#include <time.h>
#include <stdio.h>                                   
#include <stdlib.h>                                  
#include <math.h>
#include <stdio.h>
#include <iostream>
#include <iostream>
#include <string.h>
#include <sstream>
#include <queue>
using namespace std;
// ------------------------------------- OLD VERSION -------------------------------------

#include "TopSpinAStarBPMXLH.h"


const int ClassicAStar_CODE = -1;
const int IClassicAStar_CODE = -2;
const int LHASTAR1_START_CODE = 10;
const int LHAStar2_START_CODE = 40;
const int BPMXLHAStar2_START_CODE = 20;
const int BPMXLHAStar1_START_CODE = 30;
char* ClassicAStar_NAME = "A*";
int nextIDAStarBound;
bool USE_REFLECTION=true;
// ------------------------------------------------
//                  Parameters
//-------------------------------------------------

bool OperMat[SIZE+1][SIZE];/* Allowed operation table*/

//---------- Hash table definitions (total memory) --------------
long MAX = 19000000;                              /*max size of memory (hash table)*/
long FULL = 18100000;                             /* max size of open list */
 struct hashtable                                 /* table of generated states */
{                            
	short boardState[SIZE];
	short g;                                      /* distance from initial state */
	short h;                        /* static heuristic distance from goal state */
	short PrevMove;                                /* previous position of blank */
	int link;                    /* pointer to next element with same hash value */
	int heaplink;
	int cost;
	// TODO - check if the prev and next are needed
	//int prev;                            /* index of previous state in open list */
	//int next;
} old[19000000];      /* index of next state in open list, last is NIL */

 int bucket[19000000];   /* pointer to first element in table with given hash value */
 int empty;                      /* index of first free location in hash table */
 unsigned int hashPowers[SIZE][SIZE]; /* supporting vector to calculate hash value*/

//------------- Heap definitions (total memory) ----------------
int heap[18100000];
int bestf;
int bestc;

int OpenStart;         /* index of first element of OPEN list*/
int OpenEnd;			/* index of last element of open list*/


//---------------- PDB definition ------------------------------
unsigned char h1[h1_size];
int tilePosForGetH_1[PATTERNSIZE_1+1];
bool isBelongToPattern[SIZE]; /* boolean array - true for tokens included in PDB, false for tokens not included*/
int locOfPatternInTiles[SIZE];
int rotatedStateForGetH[SIZE];/*used to calculate hash */
int rotatedStateForGoal[SIZE];/*used to find goal*/

int refArr[SIZE]; /*will contain the reflection for H calculation*/
int refArr1[SIZE];
int arrRef[SIZE]={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
int CostArr[40];
//--------------- BPMX Search support parameters ---------------
int delta;

//--------------- Counters -------------------------------------
int UpperLimit;                              /* current goal best cost */
int expanded;                               /* total number of nodes expanded */
int generated;                             /* total number of nodes generated */
int stored;                                  /* total number of states stored */
int ImmediateGenerated;                      /* total number of states generated by changing the parent (without allocating mameory)*/
int IE;                                     /* total number of states expanded and entered immediatlly to the close list*/
int reopened;                              /* total number of states that were re-entered from close to open*/
int reclose;
int goalDepth;                             /* minimum number of steps from initial state to goal*/
int opened;                                /* total number of states entered to open list */
int closed;                                /* total number of states entered to close list */
int maxopen;                               /* maximum size of open list */
int copen;                                 /* supporting counter to determine maxopen*/
int duplicatCounter;                       /* number of states that already exist in memory*/
int CaseCounter;                           /* count the number of problems solved */
int FoundInC;
int FoundInO;
int NextBestF;
int NextBestC;
int LHnodes;
int BUpdate;
int LHUpdate;
int BLHUpdate;
int IGSameV;
int IGt;
int sameV;
int bigG;
int minf;
int LHFrom;
int falseLH;

double time2search;                        /* timer measuring search time for a single state-problem*/

/***************************************************************************************************/
// -------------------------------------------------
//                  Functions
//--------------------------------------------------


//------------- General utilities ------------------
void PrintResult2File(string SearchName,int lookahead)
{
	FILE *f1;
		
	f1 = fopen("AStarLH_100_TopSpin16_withSkip.csv","a");
	fprintf(f1,"%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%f\n",lookahead,CaseCounter,expanded,IE,stored,goalDepth,ImmediateGenerated,maxopen,opened,closed,duplicatCounter,reopened,time2search);
	fclose(f1);
}


void PrintResult(char* algorithmName)
{
	FILE *f1;

	f1=fopen("BPMX_100cases_16_thesis_noIE_09Nov_myH_finalll.csv","a");
	fprintf(f1,"%d,%s,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%f\n",CaseCounter,algorithmName,goalDepth,expanded,IE,stored,ImmediateGenerated,reopened,FoundInC,LHnodes,BUpdate,LHUpdate,BLHUpdate,time2search);
	fclose(f1);
}

void PrintResult(char* algorithmName,int parameter)
{
	FILE *f1;

	f1=fopen("BPMX_100cases_16_thesis_noIE_09Nov_myH_finalll.csv","a");
	fprintf(f1,"%d,",CaseCounter);
	fprintf(f1,algorithmName,parameter);
	fprintf(f1,",%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%f\n",goalDepth,expanded,IE,stored,ImmediateGenerated,reopened,FoundInC,LHnodes,BUpdate,LHUpdate,BLHUpdate,time2search);
	fclose(f1);
}

I64 CalcHash(short state[SIZE])
{

	I64 val=1;
	I64 tempval;


	for (int i=0;i<SIZE;i++)
	{
		tempval=state[i];
		val+=hashPowers[i][tempval];
	}
	//printf("%u\n",val);
	val=val%MAX;

	return val;

}


//-------------- State (changing & updaing)---------
// Function name	: MakeMove
// Description	    : This function make move iMove on state in stateIndex
// Return type		: void 
// Argument         : int stateIndex (index of the state in hash)
// Argument         : int iMove
void MakeMove(int stateIndex,int iMove)
{
	int iFrom,iTo,tmp;
	//for (iFrom = 0;iFrom<SIZE;iFrom++)
	//	out_state[iFrom] = in_state[iFrom];

	tmp = ((SPIN_SIZE-1) + iMove) % SIZE;
	int aVal = -1;
	//for(int i=0;i<= (SPIN_SIZE>>1);i++) /*original condition*/
	for(int i=0;i< (SPIN_SIZE>>1);i++)
	{
		iFrom = (iMove+i) % SIZE;
		iTo = tmp;
		int tmpV=old[stateIndex].boardState[iFrom];
		old[stateIndex].boardState[iFrom] = old[stateIndex].boardState[iTo];
		//out_state[iTo] = in_state[iFrom];
		old[stateIndex].boardState[iTo]=tmpV;
		if (tmp>SIZE)
		{
			aVal = 1;
			tmp = 0;
		}
		else
			tmp+=aVal;
		if (tmp<0)
			tmp = (SIZE-1);
	}
}

void MakeMove(short state[SIZE],int iMove)
{
	int iFrom,iTo,tmp;
	//for (iFrom = 0;iFrom<SIZE;iFrom++)
	//	out_state[iFrom] = in_state[iFrom];

	tmp = ((SPIN_SIZE-1) + iMove) % SIZE;
	int aVal = -1;
	//for(int i=0;i<= (SPIN_SIZE>>1);i++) /*original condition*/
	for(int i=0;i< (SPIN_SIZE>>1);i++)
	{
		iFrom = (iMove+i) % SIZE;
		iTo = tmp;
		int tmpV=state[iFrom];
		state[iFrom] = state[iTo];
		//out_state[iTo] = in_state[iFrom];
		state[iTo]=tmpV;
		if (tmp>SIZE)
		{
			aVal = 1;
			tmp = 0;
		}
		else
			tmp+=aVal;
		if (tmp<0)
			tmp = (SIZE-1);
	}
}

// Function name	: rotateArray
// Description	    : This function rotate the array  
// Return type		: void 
void rotateArray(int stateIndex,int newZeroLoc)
{
	int i,prevZeroLoc;
	int loc = newZeroLoc;
	prevZeroLoc = 0;
	while (old[stateIndex].boardState[prevZeroLoc]!=0)
		prevZeroLoc++;

	for (i=0; i< SIZE ; i++) //initialize sRotated with dual of State
	{
		rotatedStateForGetH[loc%SIZE] = old[stateIndex].boardState[(i + prevZeroLoc)%SIZE] ;     
		loc++;
	}
}

// Function name	: rotateArray
// Description	    : This function rotate the array  
// Return type		: void 
void rotateArrayWRef(int newZeroLoc)
{
	int i,prevZeroLoc;
	int loc = 0;
	prevZeroLoc = 0;
	while (refArr1[prevZeroLoc]!=0)
		prevZeroLoc++;

	for (i=0; i< SIZE ; i++) //initialize sRotated with dual of State
	{
		rotatedStateForGetH[loc%SIZE] = refArr1[(i + prevZeroLoc)%SIZE] ;     
		loc++;
	}
	//for(int i=0;i<SIZE;i++)
	//	printf("%d ",rotatedStateForGetH[i]);
}

void GetReflection(int iRef,int stateIndex)
{
	//printf("%s %d\n","iRef=",iRef);
	//for (int i=0;i<SIZE;i++)
	//	printf("%d ",old[stateIndex].boardState[i]);
	//printf("%s\n","");
	for (int i=0;i<SIZE;i++)
		refArr[i] = (old[stateIndex].boardState[i] + iRef) % SIZE;
	//	for (int i=0;i<SIZE;i++)
	//	printf("%d ",refArr[i]);
	//printf("%s\n","");

}

void GetReflection(int iRef,short state[SIZE])
{
	//printf("%s %d\n","iRef=",iRef);
	//for (int i=0;i<SIZE;i++)
	//	printf("%d ",old[stateIndex].boardState[i]);
	//printf("%s\n","");
	for (int i=0;i<SIZE;i++)
		refArr[i] = (state[i] + iRef) % SIZE;
	//	for (int i=0;i<SIZE;i++)
	//	printf("%d ",refArr[i]);
	//printf("%s\n","");

}

void GetReflection(int iRef)
{
	//printf("%s %d\n","iRef=",iRef);
	//for (int i=0;i<SIZE;i++)
	//	printf("%d ",old[stateIndex].boardState[i]);
	//printf("%s\n","");
	for (int i=0;i<SIZE;i++)
		refArr1[i] = (refArr[i] + iRef) % SIZE;
	//	for (int i=0;i<SIZE;i++)
	//	printf("%d ",refArr[i]);
	//printf("%s\n","");

}

bool IsGoal(int stateIndex)
{


	int i,prevZeroLoc;
	int loc = 0;
	prevZeroLoc = 0;

	while (old[stateIndex].boardState[prevZeroLoc]!=0)
		prevZeroLoc++;

	for (i=0; i< SIZE ; i++) //initialize sRotated with dual of State
	{
		rotatedStateForGoal[loc%SIZE] = old[stateIndex].boardState[(i + prevZeroLoc)%SIZE] ;     
		loc++;
	}
	bool result=true;
	for(int i=0;i<SIZE-1;i++)
	{
		if(rotatedStateForGoal[i]>rotatedStateForGoal[i+1])
		{
			//printf("%s\n","not a goal");
			result=false;
			break;
		}

	}
	//if(result) printf("%s","is goal"); 
	return result;
}

bool IsGoal(short state[SIZE])
{
	int i,prevZeroLoc;
	int loc = 0;
	prevZeroLoc = 0;

	while (state[prevZeroLoc]!=0)
		prevZeroLoc++;

	for (i=0; i< SIZE ; i++) //initialize sRotated with dual of State
	{
		rotatedStateForGoal[loc%SIZE] = state[(i + prevZeroLoc)%SIZE] ;     
		loc++;
	}
	bool result=true;
	for(int i=0;i<SIZE-1;i++)
	{
		if(rotatedStateForGoal[i]>rotatedStateForGoal[i+1])
		{
			//printf("%s\n","not a goal");
			result=false;
			break;
		}

	}
//	if(result) printf("%s","is goal"); 
	return result;

}

int FindNextBestC(int loc)
{
	int left,right,MinLeftC,MinRightC,MinC;

	//printf("%s %d %s %d %s %d\n","loc=",loc,"bestc=",bestc,"OpenStart=",OpenStart);

	if(old[heap[loc]].cost>bestc)
	{
		//printf("%s %d %s %d\n","Found it - old[heap[loc]].cost=",old[heap[loc]].cost,"stored=",stored);
		return old[heap[loc]].cost;
	}

	//printf("%s %d %s %d\n","old[heap[loc]].cost=",old[heap[loc]].cost,"stored=",stored);
	left=2*loc+1;
	right=2*loc+2;
	MinLeftC=INFINITY;
	MinRightC=INFINITY;

	if(left<=OpenStart)
	MinLeftC=FindNextBestC(left);
	if(right<=OpenStart)
	MinRightC=FindNextBestC(right);

	MinC=MIN(MinLeftC,MinRightC);

	return MinC;

}


//-------------- PDB (uploading and using)----------

// Function name	: InitPDB
// Description	    : This function uploads the PDB to memory 
//                    from a PDB file (name and path specified in TopSpinMain.h)
// Return type		: void 
void InitPDB()
{

	FILE *infile;

	// Open the PDB file
	printf("Reading PDB - %s\n",FILE1);
	infile = fopen(FILE1,"rb");

	// If file doen't exist - exit
	if (infile == NULL)
	{
		printf("Can't locate PDB...\n");
		exit(0);
	}

	// Read the file into h1
	fread(h1,sizeof(UCHAR)*h1_size,1,infile);
	fclose(infile);
}

void InitPDBParameters()
{
	I64 PatternSize;
	int acc;
	int PatArray[PATTERNSIZE_1];
	int number1;

	PatternSize = PATTERNSIZE_1;
	acc =0;

	for (int i=0;i<PATTERNSIZE_1;i++)
		PatArray[i]=i;

	for (int i=0;i<SIZE;i++)
	{
		isBelongToPattern[i]=false;
		locOfPatternInTiles[i] = -1;
	}
	//0 - the first symbol get -1     Note Symbole 0 belong to pattern automaticly
	//The second symbol get 0 
	//The 3rd get 1...

	for (int i=1;i<PatternSize;i++)
	{
		number1 = PatArray[i];
		isBelongToPattern[number1] = true;
		locOfPatternInTiles[number1] = acc;
		acc++;
	}
	printf("%s","isBelongToPattern:");
	for(int i=0;i<SIZE;i++)
		printf("%d ",isBelongToPattern[i]);
	printf("%s\n","");
		printf("%s","locOfPatternInTiles:");
	for(int i=0;i<SIZE;i++)
		printf("%d ",locOfPatternInTiles[i]);
	printf("%s\n","");


}


// Function name	: hash
// Description	    : Convarte tiles into hash Number
// Return type		: I64 
// Argument         : index of state in hash(int stateIndex), number of tokens in Pattern (int lPatternSize)
I64 hash( int lPatternSize)
{
//	PrintTiles(in_tiles);
	int i,digit,j;
	I64 hashval = 0;
	for (i = 0; i < (lPatternSize - 1); i++)                         /* for each remaining position in permutation */
    {digit = tilePosForGetH_1[i] ;                                  /* initially digit is value in permutation */
      for (j = 0; j < i; j++)                           /* for each previous element in permutation */
       if (tilePosForGetH_1[j] < tilePosForGetH_1[i]) digit--; /* previous position contains smaller value, decrement digit*/
         hashval = hashval * ((SIZE-1) - i) + digit;}              /* multiply digit by appropriate factor */
	return hashval;
}


// Function name	: ConvarteStateToTilesPos
// Description	    : 
// Return type		: void 
// Argument         : int *in_rotated_state
// Argument         : int *out_tiles
void ConvarteStateToTilesPos(int iPartition)
{
	int i;
	//for(i=0;i<SIZE;i++)
	//	tilePosForGetH_1[i]=0;
	for (i=0;i<SIZE;i++)
	{
		//printf("%s %d\n","rotatedStateForGetH[i]=",rotatedStateForGetH[i]);
		//printf("%s %d\n","isBelongToPattern[rotatedStateForGetH[i]]=",isBelongToPattern[rotatedStateForGetH[i]]);
		if (isBelongToPattern[rotatedStateForGetH[i]])
		{
			//printf("%s %d\n","locOfPatternInTiles[rotatedStateForGetH[i]]=",locOfPatternInTiles[rotatedStateForGetH[i]]);
			tilePosForGetH_1[locOfPatternInTiles[rotatedStateForGetH[i]]]=i-1;
		}
	}
}



void ShuffleArrayValues()
{
	for(int i=0;i<SIZE;i++)
	arrRef[i]=i;
		int newLoc,tmp;
	//printf("%s","arrRef before change: ");
	//for (int i=0;i<SIZE;i++)
	//	printf("%d ",arrRef[i]);
	//printf("%s\n","");

	for (int i=SIZE ; i>0; i--)
	{
		//printf("%s %d\n","i=", i);
		//printf("%s %d\n","rand()=", rand()%SIZE);
		newLoc = rand() % i;
		tmp = arrRef[i - 1];
		arrRef[i - 1] = arrRef[newLoc];
		arrRef[newLoc] = tmp;
	}

}

// Function name	: GetHuristicRegular
// Description	    : Returns The Huristic Value from PDB
// Return type		: UCHAR 
// Argument         : index of the state to evaluate (int stateIndex)
UCHAR GetHuristicRegular(int stateIndex,int iPartition)
{
	UCHAR val;
	//h_r_Ret = 0;
	I64 hashVal,entry;


	//Random a token number

	int sum=0;
	
	for(int i=0;i<SIZE;i++)
		sum=sum+old[stateIndex].boardState[i]*i;
	int iToken=0;
	if (USE_REFLECTION){
		iToken=sum%SIZE;
	}
	//srand(sum*1000);

	//Perform reflection to re-order the tokens
	GetReflection(iToken,stateIndex);

	//GetReflection(0,stateIndex);
	int hmax=0;
	int zTile;
	for(int i=0;i<1;i++)
	{
		zTile=h_PTiles[i][0];
		GetReflection(SIZE-zTile);
		rotateArrayWRef(0);
		ConvarteStateToTilesPos(iPartition);
		hashVal=hash(PATTERNSIZE_1);
		val = h1[hashVal];
		hmax=MAX(hmax,val);
	}
	return hmax;
}


UCHAR GetHuristicRegular(short state[SIZE],int iPartition)
{
	UCHAR val;
	//h_r_Ret = 0;
	I64 hashVal,entry;


	//Random a token number
	
	int sum=0;
	for(int i=0;i<SIZE;i++)
		sum=sum+state[i]*i;
	int iToken=0;
	if (USE_REFLECTION){
		iToken=sum%SIZE;
	}
	//Perform reflection to re-order the tokens
	GetReflection(iToken,state);
	//GetReflection(0,stateIndex);


	int hmax=0;
	int zTile;
	for(int i=0;i<1;i++)
	{
		zTile=h_PTiles[i][0];
		GetReflection(SIZE-zTile);
		rotateArrayWRef(0);
		ConvarteStateToTilesPos(iPartition);
		hashVal=hash(PATTERNSIZE_1);
		val = h1[hashVal];
		hmax=MAX(hmax,val);
	}
	return hmax;
}







// Function name	: initshouldSkipOperMat
// Description	    : This function initialize shouldSkipOperMat
//                    If we should expend son acourding to pop
//                    will contain 
// Return type		: void 
void initshouldSkipOperMat()
{
	int oldMove,newMove;
	int acc;
	for (oldMove=0;oldMove<=SIZE;oldMove++)
		for (newMove=0;newMove<SIZE;newMove++)
			OperMat[oldMove][newMove] = true; //should always make

		for (oldMove=0;oldMove<SIZE;oldMove++)
		{
			acc =0;
			for (newMove = oldMove;newMove<SIZE;newMove++)
			{
				if (newMove==oldMove || acc >=SPIN_SIZE && acc <= SIZE-SPIN_SIZE)
					OperMat[newMove][oldMove] = false;
				acc++;
			}
		}
	
		printf("SKIP ON True\n\n");
		for (int i=0;i<=SIZE;i++)
		{
			for(int j=0;j<SIZE;j++)
				if (OperMat[i][j])
					printf("T ");
				else
					printf("F ");
			printf("\n");
		}
}

//void oShuffleArrayValues()
//{
//		int newLoc,tmp;
//	//printf("%s","arrRef before change: ");
//	//for (int i=0;i<SIZE;i++)
//	//	printf("%d ",arrRef[i]);
//	//printf("%s\n","");
//
//	for (int i=SIZE ; i>0; i--)
//	{
//		//printf("%s %d\n","i=", i);
//		//printf("%s %d\n","rand()=", rand()%SIZE);
//		newLoc = rand() % i;
//		tmp = arrRef[i - 1];
//		arrRef[i - 1] = arrRef[newLoc];
//		arrRef[newLoc] = tmp;
//	}
//
//}

//----- Heap activities (hash, insert, delete) --------
void Heapify_up(int iloc)
{
	int parent;
	int parentg;
	int parentf;
	int child;
	int childg;
	int childf;

	parent=floor((double)(iloc-1)/2);
	parentg=old[heap[parent]].g;
	parentf=parentg+old[heap[parent]].h;

	child=iloc;
	childg=old[heap[child]].g;
	childf=old[heap[child]].h+childg;

	if(parent<0) return;
	if(parentf>childf || (parentf==childf && childg>=parentg))
	{
		//printf("%s\n","switching");
		int temp=heap[parent];
		old[heap[parent]].heaplink=child;
		old[heap[child]].heaplink=parent;
		heap[parent]=heap[child];
		heap[child]=temp;
		
		Heapify_up(parent);
	}

}

void Heapify(int iloc)
{
	int right;
	int left;

	int rightf;
	int rightg;

	int leftf;
	int leftg;

	int itemf;
	int itemg;

	int minCost=iloc;

	right=2*iloc+2;
	left=2*iloc+1;


	itemf=old[heap[iloc]].g+old[heap[iloc]].h;
	itemg=old[heap[iloc]].g;

	if(right<= OpenStart)
	{
		rightf=old[heap[right]].g+old[heap[right]].h;
		rightg=old[heap[right]].g;
		
	}
	if (left<=OpenStart)
	{
		leftf=old[heap[left]].g+old[heap[left]].h;
		leftg=old[heap[left]].g;

	}


	if(left<=OpenStart && (leftf<itemf || (itemf==leftf && leftg>=itemg)))
	{
		minCost=left;
	}
	else
	{
		minCost=iloc;
	}

	if(right<=OpenStart && (rightf<old[heap[minCost]].h+old[heap[minCost]].g || (old[heap[minCost]].h+old[heap[minCost]].g==rightf && rightg>=old[heap[minCost]].g)))
	{
		minCost=right;
	}


		if(minCost!=iloc)
		{
			old[heap[iloc]].heaplink=minCost;
			old[heap[minCost]].heaplink=iloc;
			int temp=heap[iloc];
			heap[iloc]=heap[minCost];
			heap[minCost]=temp;
			Heapify(minCost);
		}


}




void FHeapify_up(int iloc)
{
	int parent;
	int parentc;
	int parentg;
	int parentf;
	int child;
	int childg;
	int childc;
	int childf;

	//printf("%s %d\n","iloc=",iloc);
	parent=floor((double)(iloc-1)/2);
	parentg=old[heap[parent]].g;
	parentf=parentg+old[heap[parent]].h;
	parentc=old[heap[parent]].cost;

	child=iloc;
	childg=old[heap[child]].g;
	childc=old[heap[child]].cost;
	childf=old[heap[child]].g+old[heap[child]].h;

	if(parent<0) 
	{
	//	printf("%s\n","parent<0");
		return;
	}
	//if(parentc>childc || (parentc==childc && childf<=parentf))
	if(parentc>childc || (parentc==childc && childf<parentf) || (parentc==childc && childf==parentf && childg>=parentg))//)
	{
		//printf("%s %d %s %d\n","parentc=",parentc,"childc=",childc);
		//if(heap[child]==25|| heap[parent]==25||heap[child]==137|| heap[parent]==137) printf("%s %d %s %d\n","switching-",heap[parent]," with-",heap[child]);
		int temp=heap[parent];
		old[heap[parent]].heaplink=child;
		old[heap[child]].heaplink=parent;
		heap[parent]=heap[child];
		heap[child]=temp;
		
		FHeapify_up(parent);
	}
	else
	{
		//printf("%s\n","not switching");
	}

}

void FHeapify(int iloc)
{
	int right;
	int left;

	int rightf;
	int rightc;
	int rightg;

	int leftf;
	int leftc;
	int leftg;

	int itemf;
	int itemc;
	int itemg;

	int minCost=iloc;

	right=2*iloc+2;
	left=2*iloc+1;


	itemf=old[heap[iloc]].g+old[heap[iloc]].h;
	itemc=old[heap[iloc]].cost;
	itemg=old[heap[iloc]].g;

	//printf("%s %d %s %d %s %d\n","right=",right,"left=",left,"OpenStart=",OpenStart);
	if(right<= OpenStart)
	{
		rightf=old[heap[right]].g+old[heap[right]].h;
		rightc=old[heap[right]].cost;
		rightg=old[heap[right]].g;
		//printf("%s %d %s %d %s %d\n","rightf=",rightf,"rightc=",rightc,"rightg=",rightg);
		
	}
	if (left<=OpenStart)
	{
		leftf=old[heap[left]].g+old[heap[left]].h;
		leftc=old[heap[left]].cost;
		leftg=old[heap[left]].g;
		//printf("%s %d %s %d %s %d\n","leftf=",leftf,"leftc=",leftc,"rightg=",leftg);

	}


	//if(left<=OpenStart && (leftc<itemc || (itemc==leftc && leftf<=itemf)))
	if(left<=OpenStart && (leftc<itemc || (itemc==leftc && leftf<itemf) ||(itemc==leftc && leftf==itemf && leftg>=itemg )))
	{
		minCost=left;
	}
	else
	{
		minCost=iloc;
	}
	//if(right<=OpenStart  && (rightc<old[heap[minCost]].cost || (old[heap[minCost]].cost==rightc && rightf<=old[heap[minCost]].g+old[heap[minCost]].h)))
	if(right<=OpenStart  && (rightc<old[heap[minCost]].cost || (old[heap[minCost]].cost==rightc && rightf<old[heap[minCost]].g+old[heap[minCost]].h) || (old[heap[minCost]].cost==rightc && rightf==old[heap[minCost]].g+old[heap[minCost]].h && rightg>=old[heap[minCost]].g)))
	{
		minCost=right;
	}


	//printf("%s %d %s %d\n","minCost=",minCost,"iloc=",iloc);
		if(minCost!=iloc)
		{
			old[heap[iloc]].heaplink=minCost;
			old[heap[minCost]].heaplink=iloc;
			int temp=heap[iloc];
			heap[iloc]=heap[minCost];
			heap[minCost]=temp;
			FHeapify(minCost);
		}


}

void FFHeapify_up(int iloc)
{
	int parent;
	int parentg;
	int parentf;
	int parentc;
	int child;
	int childg;
	int childf;
	int childc;

	parent=floor((double)(iloc-1)/2);
	parentg=old[heap[parent]].g;
	parentf=parentg+old[heap[parent]].h;
	parentc=old[heap[parent]].cost;

	child=iloc;
	childg=old[heap[child]].g;
	childf=old[heap[child]].h+childg;
	childc=old[heap[child]].cost;

	if(parent<0) return;
	if(parentf>childf || (parentf==childf && childc<parentc) || (parentf==childf && childc==parentc && childg>=parentg))
	{
		//printf("%s\n","switching");
		int temp=heap[parent];
		old[heap[parent]].heaplink=child;
		old[heap[child]].heaplink=parent;
		heap[parent]=heap[child];
		heap[child]=temp;
		
		FFHeapify_up(parent);
	}

}

void FFHeapify(int iloc)
{
	int right;
	int left;

	int rightf;
	int rightc;
	int rightg;

	int leftf;
	int leftc;
	int leftg;

	int itemf;
	int itemc;
	int itemg;

	int minCost=iloc;

	right=2*iloc+2;
	left=2*iloc+1;


	itemf=old[heap[iloc]].g+old[heap[iloc]].h;
	itemg=old[heap[iloc]].g;
	itemc=old[heap[iloc]].cost;

	if(right<= OpenStart)
	{
		rightf=old[heap[right]].g+old[heap[right]].h;
		rightg=old[heap[right]].g;
		rightc=old[heap[right]].cost;
		
	}
	if (left<=OpenStart)
	{
		leftf=old[heap[left]].g+old[heap[left]].h;
		leftg=old[heap[left]].g;
		leftc=old[heap[left]].cost;

	}


	if(left<=OpenStart && (leftf<itemf || (itemf==leftf && leftc<itemc) || (itemf==leftf && leftc==itemc && leftg>=itemg)))
	{
		minCost=left;
	}
	else
	{
		minCost=iloc;
	}

	if(right<=OpenStart && (rightf<old[heap[minCost]].h+old[heap[minCost]].g || (old[heap[minCost]].h+old[heap[minCost]].g==rightf && rightc<old[heap[minCost]].cost) || (old[heap[minCost]].h+old[heap[minCost]].g==rightf && rightc==old[heap[minCost]].cost && rightg>=old[heap[minCost]].g)))
	{
		minCost=right;
	}


		if(minCost!=iloc)
		{
			old[heap[iloc]].heaplink=minCost;
			old[heap[minCost]].heaplink=iloc;
			int temp=heap[iloc];
			heap[iloc]=heap[minCost];
			heap[minCost]=temp;
			FFHeapify(minCost);
		}


}





//----- Hash activities (hash, insert, delete) --------

// Function name	: initHashPow
// Description	    : This function initialize the supporting vector hashPowers (helps to calculate hash value)
//                    will contain 
// Return type		: void
void initHashPow()
{
	for (int i=0;i<SIZE;i++)
	{
		for (int j=0;j<SIZE;j++)
		{
			hashPowers[i][j]=(unsigned int)(pow((float)SIZE,i)*j);
			//printf("%u ",hashPowers[i][j]);
		}
		//printf("%s\n","");
	}
}




int SearchHash (short state2search[SIZE],int hashval)


{int index;                        /* index to different states in hash table */
 int pos;                            /* index to different positions in state */


 index = bucket[hashval];                     /* first state in target bucket */

 while (index != MAX)                         /* end of chain not reached yet */
   {
	   for (pos = 0; pos < SIZE; pos++)           /* each position in the state */
      if (state2search[pos] != old[index].boardState[pos] ||old[index].g==-1 ) break;    /* mismatch: exit for loop */
    if (pos == SIZE)
	{
		//printf("%s","found array:");
		//for (int i=0;i<SIZE;i++)
		//	printf("%d ",old[index].boardState[i]);
		//printf("%s\n","");
		return (index);         /* state found, return location */
	}
    else index = old[index].link;}                     /* next state on chain */

 
return (-1);}



void InsertHash (int parentNode,int hashval,int PrevMove, int g, int h)

{
	//int word;                                            /* word in packed state */
	 int f;                                            /* combined merit function - no need - BFS*/
	 int index;                           /* index in hash table where state goes */

	 index = empty++;           /* store in first empty location , empty defined globaly */
	 stored++;                        /* increment number of states in hash table */
	 opened++;
	 copen++;
	 if(maxopen<copen) maxopen=copen;

	for (int i=0;i<SIZE;i++)
	{
		if(old[parentNode].boardState[i]==-2) printf("%s\n","we have an issue");
		old[index].boardState[i]=old[parentNode].boardState[i];
	}
	old[index].PrevMove=PrevMove;
	

	//3. update h & g
	old[index].g=g;
	old[index].h=h;
	 
	

	 //TODO - need to re-think the assigment of the hash list per hashvalue (instead of adding the last node first, add it to the end of the list)
	 old[index].link = bucket[hashval];      /* next pointer to old first element */
	 bucket[hashval] = index;               /* new state is at head of hash chain */
	 f = old[index].g + old[index].h;


		//Heap OPEN list
		
	OpenStart++;

	heap[OpenStart]=index;
	old[index].heaplink=OpenStart;
	Heapify_up(OpenStart);

    if (f < bestf) bestf = f;

}

void FInsertHash (int parentNode,int hashval,int PrevMove, int g, int h,int cost)

{
	//int word;                                            /* word in packed state */
	 int f;                                            /* combined merit function - no need - BFS*/
	 int index;                           /* index in hash table where state goes */


	 index = empty++;           /* store in first empty location , empty defined globaly */
	 stored++;                        /* increment number of states in hash table */
	 opened++;
	 copen++;
	 if(maxopen<copen) maxopen=copen;

	 //printf("%s %d %s %d %s %d\n","adding - g=",g,"h=",h,"cost=",cost);
	 if(cost<g+h)
	 {
		 printf("%s %d %s %d\n","issue - f=",g+h," cost=",cost);
		 string mystr;
			getline (cin,mystr);
	 }
	// printf("%s %d\n","index=",index);
	for (int i=0;i<SIZE;i++)
	{
		old[index].boardState[i]=old[parentNode].boardState[i];
	}
	old[index].PrevMove=PrevMove;
	old[index].cost=cost;
	

	//3. update h & g
	old[index].g=g;
	old[index].h=h;
	 
	

	 //TODO - need to re-think the assigment of the hash list per hashvalue (instead of adding the last node first, add it to the end of the list)
	 old[index].link = bucket[hashval];      /* next pointer to old first element */
	 bucket[hashval] = index;               /* new state is at head of hash chain */
	 f = old[index].g + old[index].h;


		//Heap OPEN list
		
	OpenStart++;

	//printf("%s %d\n","OpenStart=",OpenStart);
	heap[OpenStart]=index;
	old[index].heaplink=OpenStart;
	FHeapify_up(OpenStart);
	//Heapify_up(OpenStart);


	//if(index==192 || index==193 || index==137||index==25)
	//{
	//for(int i=0;i<OpenStart;i++)
	//{
		//if((heap[2*i+1]!=-1 || heap[2*i+2]!=-1) && (old[heap[i]].cost>old[heap[2*i+1]].cost || old[heap[i]].cost>old[heap[2*i+2]].cost))
		//{
		//	printf("%d %s%d %s%d %s%d %s%d %s%d %s%d %s%d %s%d %s%d %s%d %s%d %s%d\n",i,"|",old[heap[i]].cost,"|",old[heap[i]].g,"|",old[heap[i]].h,"|",old[heap[2*i+1]].cost,"|",old[heap[2*i+1]].g,"|",old[heap[2*i+1]].h,"|",old[heap[2*i+2]].cost,"|",old[heap[2*i+2]].g,"|",old[heap[2*i+2]].h,"|",heap[i],"|",heap[2*i+1],"|",heap[2*i+2]);
		//}
	//}
	//string mystr;
	//getline (cin,mystr);
	//}
	//printf("%s %d %s\n","---end of node--",index,"---");
	
    if (f < bestf) bestf = f;

}

void FInsertHash2 (short state[SIZE],int hashval,int PrevMove, int g, int h,int cost)

{
	//int word;                                            /* word in packed state */
	 int f;                                            /* combined merit function - no need - BFS*/
	 int index;                           /* index in hash table where state goes */


	 index = empty++;           /* store in first empty location , empty defined globaly */
	 stored++;                        /* increment number of states in hash table */
	 opened++;
	 copen++;
	 if(maxopen<copen) maxopen=copen;

	 //printf("%s %d %s %d %s %d\n","adding - g=",g,"h=",h,"cost=",cost);
	 if(cost<g+h)
	 {
		 printf("%s %d %s %d\n","issue - f=",g+h," cost=",cost);
		 string mystr;
			getline (cin,mystr);
	 }
	// printf("%s %d\n","index=",index);
	for (int i=0;i<SIZE;i++)
	{
		old[index].boardState[i]=state[i];
	}
	old[index].PrevMove=PrevMove;
	old[index].cost=cost;
	

	//3. update h & g
	old[index].g=g;
	old[index].h=h;
	 
	

	 //TODO - need to re-think the assigment of the hash list per hashvalue (instead of adding the last node first, add it to the end of the list)
	 old[index].link = bucket[hashval];      /* next pointer to old first element */
	 bucket[hashval] = index;               /* new state is at head of hash chain */
	 f = old[index].g + old[index].h;


		//Heap OPEN list
		
	OpenStart++;

	//printf("%s %d\n","OpenStart=",OpenStart);
	heap[OpenStart]=index;
	old[index].heaplink=OpenStart;
	FHeapify_up(OpenStart);
	//Heapify_up(OpenStart);


	//if(index==192 || index==193 || index==137||index==25)
	//{
	//for(int i=0;i<OpenStart;i++)
	//{
		//if((heap[2*i+1]!=-1 || heap[2*i+2]!=-1) && (old[heap[i]].cost>old[heap[2*i+1]].cost || old[heap[i]].cost>old[heap[2*i+2]].cost))
		//{
		//	printf("%d %s%d %s%d %s%d %s%d %s%d %s%d %s%d %s%d %s%d %s%d %s%d %s%d\n",i,"|",old[heap[i]].cost,"|",old[heap[i]].g,"|",old[heap[i]].h,"|",old[heap[2*i+1]].cost,"|",old[heap[2*i+1]].g,"|",old[heap[2*i+1]].h,"|",old[heap[2*i+2]].cost,"|",old[heap[2*i+2]].g,"|",old[heap[2*i+2]].h,"|",heap[i],"|",heap[2*i+1],"|",heap[2*i+2]);
		//}
	//}
	//string mystr;
	//getline (cin,mystr);
	//}
	//printf("%s %d %s\n","---end of node--",index,"---");
	
    if (f < bestf) bestf = f;

}

//void oldInsertHash2(short state[SIZE],int hashval,int PrevMove, int g, int h)
//{
//	//int word;                                            /* word in packed state */
//	 int f;                                            /* combined merit function - no need - BFS*/
//	 int index;                           /* index in hash table where state goes */
//
//
//	 index = empty++;           /* store in first empty location , empty defined globaly */
//	 stored++;                        /* increment number of states in hash table */
//	 opened++;
//	 copen++;
//	 if(maxopen<copen) maxopen=copen;
//
//	for (int i=0;i<SIZE;i++)
//	{
//		old[index].boardState[i]=state[i];
//	}
//	old[index].PrevMove=PrevMove;
//	
//
//	//3. update h & g
//	old[index].g=g;
//	old[index].h=h;
//	 
//	
//
//	 //TODO - need to re-think the assigment of the hash list per hashvalue (instead of adding the last node first, add it to the end of the list)
//	 old[index].link = bucket[hashval];      /* next pointer to old first element */
//	 bucket[hashval] = index;               /* new state is at head of hash chain */
//	 f = old[index].g + old[index].h;
//
//
//		//Heap OPEN list
//		
//	OpenStart++;
//
//	heap[OpenStart]=index;
//	old[index].heaplink=OpenStart;
//	Heapify_up(OpenStart);
//
//    if (f < bestf) bestf = f;
//
//}

void DeleteFromOpenList (int index)
{
//	int current;                                      /* current index in search */
    int f;                                     /* F value of state to be deleted */
    int next;                                 /* pointer to next element in list */
	//FILE *solution;

 f = old[index].g + old[index].h;       /* compute F value of state */
 closed++;
 copen--;
 //if(index==173974) printf("%s\n","deleting");
 ////DELETE from HEAP	
 int ploc=old[index].heaplink;//the parent location in the heap array
 old[index].heaplink=-1;
 int child;
 //printf("%s %d\n","ploc=",ploc);
 if(ploc>OpenStart || ploc<0)
 {
	 //printf("%s\n","No such element");

 }
 else
 {
	 heap[ploc]=heap[OpenStart];
	 old[heap[OpenStart]].heaplink=ploc;
	 OpenStart--;
	 Heapify(ploc);

 }

}


void FDeleteFromOpenList (int index)
{
	int current;                                      /* current index in search */
    int f;                                     /* F value of state to be deleted */
    int next;                                 /* pointer to next element in list */
	FILE *solution;

 f = old[index].g + old[index].h;       /* compute F value of state */
 closed++;
 copen--;
 ////DELETE from HEAP	
 int ploc=old[index].heaplink;//the parent location in the heap array
 //printf("%s %d %s %d\n","index=",index,"ploc=",ploc);
 //printf("%s\n","deleting");
 old[index].heaplink=-1;
 //old[index].cost=-1;
 int child;
 //printf("%s %d\n","ploc=",ploc);
 if(ploc>OpenStart || ploc<0)
 {
	 //printf("%s\n","No such element");

 }
 else
 {
	 heap[ploc]=heap[OpenStart];
	 old[heap[OpenStart]].heaplink=ploc;
	 OpenStart--;
	 FHeapify(ploc);
	 //Heapify(ploc);

 }
		//string mystr;
		//getline (cin,mystr);
}


void Add2Close(int parentNode,int hashval,int PrevMove, int g, int h)
{
	int index;
	
	index = empty++;           /* store in first empty location , empty defined globaly */
	stored++; 
	closed++;
	//IE++;

	for (int i=0;i<SIZE;i++)
	{
		old[index].boardState[i]=old[parentNode].boardState[i];
	}
	old[index].PrevMove=PrevMove;

	//3. update h & g
	old[index].g=g;
	old[index].h=h;


	 //TODO - need to re-think the assigment of the hash list per hashvalue (instead of adding the last node first, add it to the end of the list)
	 old[index].link = bucket[hashval];      /* next pointer to old first element */
	 bucket[hashval] = index;               /* new state is at head of hash chain */
	 //old[index].prev=MAX;

}

int FAdd2Close(int parentNode,int hashval,int PrevMove, int g, int h,int cost)
{
	int index;
	
	index = empty++;           /* store in first empty location , empty defined globaly */
	stored++; 
	closed++;
	//IE++;

	for (int i=0;i<SIZE;i++)
	{
		old[index].boardState[i]=old[parentNode].boardState[i];
	}
	old[index].PrevMove=PrevMove;

	//3. update h & g
	old[index].g=g;
	old[index].h=h;
	old[index].cost=cost;


	 //TODO - need to re-think the assigment of the hash list per hashvalue (instead of adding the last node first, add it to the end of the list)
	 old[index].link = bucket[hashval];      /* next pointer to old first element */
	 bucket[hashval] = index;               /* new state is at head of hash chain */
	 //old[index].prev=MAX;
return index;
}

int FAdd2Close(short state[SIZE],int hashval,int PrevMove, int g, int h,int cost)
{
	int index;
	
	index = empty++;           /* store in first empty location , empty defined globaly */
	stored++; 
	closed++;
	//IE++;

	for (int i=0;i<SIZE;i++)
	{
		old[index].boardState[i]=state[i];
	}
	old[index].PrevMove=PrevMove;

	//3. update h & g
	old[index].g=g;
	old[index].h=h;
	old[index].cost=cost;


	 //TODO - need to re-think the assigment of the hash list per hashvalue (instead of adding the last node first, add it to the end of the list)
	 old[index].link = bucket[hashval];      /* next pointer to old first element */
	 bucket[hashval] = index;               /* new state is at head of hash chain */
	 //old[index].prev=MAX;
return index;
}

int Add2Close(short state[SIZE],int hashval,int PrevMove, int g, int h)
{
	int index;
	
	index = empty++;           /* store in first empty location , empty defined globaly */
	stored++; 
	closed++;
	//IE++;

	for (int i=0;i<SIZE;i++)
	{
		old[index].boardState[i]=state[i];
	}
	old[index].PrevMove=PrevMove;

	//3. update h & g
	old[index].g=g;
	old[index].h=h;


	 //TODO - need to re-think the assigment of the hash list per hashvalue (instead of adding the last node first, add it to the end of the list)
	 old[index].link = bucket[hashval];      /* next pointer to old first element */
	 bucket[hashval] = index;               /* new state is at head of hash chain */
	 //old[index].prev=MAX;
	 //printf("%s %d\n","returning index ",index);
	 return index;

}



//-------------- Search activities --------------------
int BLookahead(int stateIndex,int g, int h, int lookahead, int PrevMove)
{
	int opindex;
	int newblank;
	int newg;
	int newh;
	int rh;
	int maxH;



	rh=0;
	maxH=0;
	if(g==0) printf("%s %d\n","parent h=",h);

	if (h+g>lookahead)
	{
		//printf("%s\n","f bigger than lookahead, returning h");
		//for(int i=0;i<SIZE;i++)
		//	printf("%d ",old[stateIndex].boardState[i]);
		//printf("%s %d\n","h=",h);
		//printf("%s\n","");
		return h;//return 1000; // the cost is higher than the lookahead level - need to rollback
	}
	if (h==0 && IsGoal(stateIndex))
	{
		if (g<UpperLimit) UpperLimit=g;
		//printf("%s %d\n","goal depth is: ",g);
		//printf("%s %d %s %d\n","ph=",old[stateIndex].h," pg=",old[stateIndex].g);
		//return -1; //do we need it? I think we do otherwise it will continue on
		return h;
	}

	//if the cost is lower than lookahead and the state is not goal - need to develope its children
	for (opindex = 0; opindex < SIZE; opindex++)
	{

		if (!OperMat[PrevMove][opindex]) // 0 -> 4 -> 8
				continue;

		newblank=opindex;
		MakeMove(stateIndex,opindex); //generate a child
		//printf("%s","Goining deeper: ");
		//for (int i=0;i<SIZE;i++)
		//	 printf("%d ",old[stateIndex].boardState[i]);
		//printf("%s\n","");

		 ImmediateGenerated++;

		 newh=GetHuristicRegular(stateIndex,0); //calculate child h

		 newg=g+1; // calculate child g
		 if(newg==1){
		//printf("%s %d %s %d\n"," g=",newg," h=",newh);
		// string mystr1;
		//getline (cin,mystr1);
		 }
		 if(newg+newh<UpperLimit )//&& newg+newh<=lookahead) // if the child cost is lower than the current goal - perform DFS
		 {
			 rh=BLookahead(stateIndex,newg,newh,lookahead,newblank);
		 }
		// printf("%s","Reversing back: ");
		// for (int i=0;i<SIZE;i++)
		//	 printf("%d ",old[stateIndex].boardState[i]);

		 MakeMove(stateIndex,opindex);
		//printf("%s\n","");
		//printf("%s %d %s %d %s %d %s %d\n","g=",g," newg=",newg," h=",h," rh=",rh);
		//getline (cin,mystr);
		 //if(g==0)
		 //{
			// maxH=MAX(maxH,rh);
			// h=maxH;
		 //}
		 //else
		 h=MAX(h,rh-1);
		 if(g==0)
		 {
		 //printf("%s %d\n","updated h=",h);
		// string mystr2;
	//getline (cin,mystr2);
		 }
		 if(g+h>lookahead)
		 {
		//	 printf("%s %d %s %d %s %d %s %d\n","h after update=",h," g=",g," newg=",newg, " lookahead=",lookahead);
			 return h;
		 }
		 	 
		 		 
	}//end for
	if(g==0)
	{
	printf("%s %d \n","--end FOR--h after update=",h);
	//string mystr;
	//getline (cin,mystr);
	}

return h;
}//End BLookahead

int IExpandNode(int stateIndex,int g,int h,int lookahead, int PrevMove)
{
	int blank;
	int newblank;
	int newindex;
	int opindex;

	int newg;
	int newh;
	int newf;
	int tile;
	int flag=-1;

	int hashval;

	FILE *solution;


	for (opindex = 0; opindex < SIZE; opindex++)
	{
		if (!OperMat[PrevMove][opindex])// 0 -> 4 -> 8
		 {
			 //printf("%s %d\n","not allowed move: ",opindex);
			continue;
		}
		//if(PrevMove==opindex) continue;

		newblank=opindex;
		MakeMove(stateIndex,opindex);
		newh=GetHuristicRegular(stateIndex,0);
		bool test=true;
		//short testa[SIZE]={2,3,4,5,6,7,8,9,10,11,12,13,14,15,0,1};
		//short testa[SIZE]={4,10,6,11,2,13,5,9,12,14,3,7,1,0,15,8};
		//short testa[SIZE]={4,10,6,11,2,13,5,9,12,14,3,7,8,15,0,1};
		//short testa[SIZE]={4,10,6,11,2,13,5,9,12,8,7,3,14,15,0,1};
		////short testa[SIZE]={4,10,6,11,2,13,5,7,8,12,9,3,14,15,0,1};
		//for (int y=0;y<SIZE;y++)
		//	if (old[stateIndex].boardState[y]!=testa[y])
		//	{
		//		test=false;
		//		break;
		//	}
		//	if (test)
		//	{
		//		printf("%s","found array: ");
		//		for (int y=0;y<SIZE;y++)
		//			printf("%d ",old[stateIndex].boardState[y]);
		//		printf("%s\n","");
		//		printf("%s %d %s %d\n","h=", newh," g=",newg);
		//		printf("%s %d\n","parent g=",old[stateIndex].g);
		//	}
		//if(abs(newh-h)>1)
		//{
		//	printf("%s %d %s %d\n","Found incos! newh=",newh," h=",h);
		//	string mystr11;
		//	 getline (cin,mystr11);

		//}
		 newg=g+1;

		 newf=newh+newg;
		 //printf("%s %d %s %d %s %d %s %d\n","newg=",newg," newh=",newh," newf=",newf," UpperLimit=",UpperLimit);

		 //string mystr;
		 //getline (cin,mystr);

		 if(newf<UpperLimit)
		 {


				//check if the changed node is a goal
				if(newh==0 && IsGoal(stateIndex))
				{
					//TODO-debug printing
					printf("%s\n","found a goal");
					printf("%s","f=");
					printf("%d\n",newf);
					printf("%s\n","");
					printf("%s","g=");
					printf("%d\n",newg);
					printf("%s\n","");
					printf("%s","The goal state is: ");
					for (int b=0;b<SIZE;b++)
						printf("%d ",old[stateIndex].boardState[b]);
					printf("%s\n","");

					//printf("%s"," rotatedStateForGetH= ");
					//for(int b=0;b<SIZE;b++)
					//	printf("%d ",rotatedStateForGetH[b]);
					//printf("%s\n","");
					//string mystr;
					//getline (cin,mystr);

					//			 					if(CaseCouter==4){
					//solution=fopen("solution_41.txt","a");
					//		fprintf(solution,"%s ","goal,");
					//		for (int i=0;i<BOARDSIZE;i++)
					//			fprintf(solution,"%d ",old[stateIndex].boardState[i]);
					//		fprintf(solution,",%d,%d,%d,%d,%d\n",newg,newh,stateIndex,newf,lookahead);
					//		fclose(solution);
					//}

					UpperLimit=newf;
					goalDepth=newf;
					

					//return 100; //?
				}

				//Calc hash and check if already exists
				hashval=CalcHash(old[stateIndex].boardState);
				newindex=SearchHash(old[stateIndex].boardState,hashval);
				if(newindex==stateIndex) newindex=-1;

				//if the current child has cost which is equal or less than the root cost -> add it to the close list and continue developing its children
				if(newf<=old[stateIndex].g+old[stateIndex].h)
				{
						if(newindex==-1)
						{
							//TODO - debug printing
							/*printf("%s","Adding the following to close list: ");
							for(int q=0;q<BOARDSIZE;q++)
								printf("%d ",old[stateIndex].boardState[q]);
							printf("%s\n","");
							printf("%s","f= ");
							printf("%d\n",newf);
							//string mystr;
							//getline (cin,mystr);*/
							//TODO-print to file
							//if(CaseCouter==4 )
							//{
							//solution=fopen("solution_41.txt","a");
							//fprintf(solution,"%s ","c,");
							//for (int i=0;i<BOARDSIZE;i++)
							//	fprintf(solution,"%d ",old[stateIndex].boardState[i]);
							//fprintf(solution,",%d,%d,%d,%d,%d\n",newg,newh,stateIndex,newf,lookahead);
							//fclose(solution);
							//}

							Add2Close(stateIndex, hashval,newblank,newg,newh);
							flag=0;
							if(IExpandNode(stateIndex,newg,newh,lookahead,newblank)==100) return 100;
						}//end if newindex
						else
						{
							//if(test) printf("%s\n","duplicate a");
							duplicatCounter++;
							if (old[newindex].g>newg)
							{
								//if(test) printf("%s\n","updating");
								/*printf("%s","newg=");
								printf("%d\n",newg);
								printf("%s","old[newindex].g=");
								printf("%d\n",old[newindex].g);*/
								//if(CaseCouter==4 )
								//{
								//solution=fopen("solution_41.txt","a");
								//fprintf(solution,"%s ","ro,");
								//for (int i=0;i<BOARDSIZE;i++)
								// fprintf(solution,"%d ",old[stateIndex].boardState[i]);
								//fprintf(solution,",%d,%d,%d,%d,%d\n",newg,newh,stateIndex,newf,lookahead);
								//fclose(solution);
								//}
								//DeleteAndUpdate(newindex,g,h);//need to update
								//printf("%s\n","deleting from IExapnd");
								if(old[newindex].heaplink==-1)
								{
									//printf("%s","array in close (newf<=f): ");
									//for (int i=0;i<SIZE;i++)
									//	printf("%d ",old[newindex].boardState[i]);
									//printf("%s\n","");
									//printf("%s %d %s %d\n","the index is: ",newindex," OpenStart is: ", OpenStart);
									//printf("%s","array in check: ");
									//for (int i=0;i<SIZE;i++)
									//	printf("%d ",old[stateIndex].boardState[i]);
									//printf("%s\n","");
									//printf("%s %d %s %d\n","old f=",old[newindex].h+old[newindex].g," newf=",newf);
									//string mystr;
							         //getline (cin,mystr);
									reopened++;
								}
								DeleteFromOpenList(newindex);
								//old[newindex].g=newg;
								//old[newindex].h=newh;
								//Add2Close(stateIndex, hashval, newblank,newblank,newg,newh);
								flag=0;

								if(IExpandNode(stateIndex,newg,newh,lookahead,newblank)==100) return 100;
							}
							//TODO-print to file
							/*solution=fopen("solution_703_7.txt","a");
							fprintf(solution,"%s ","d,");
							for (int i=0;i<BOARDSIZE;i++)
							 fprintf(solution,"%d ",old[stateIndex].boardState[i]);
							 fprintf(solution,",%d,%d,%d,%d,%d\n",newg,newh,stateIndex,newf,lookahead);
							fclose(solution);*/
							//TODO - debug printing
							//printf("%s","Already exists in close list: ");
							//for(int q=0;q<BOARDSIZE;q++)
							//	printf("%d ",old[stateIndex].boardState[q]);
							//printf("%s\n","");
							//string mystr;
							//getline (cin,mystr);

						}
						//if(flag==0)IExpandNode(stateIndex,newg,newh,lookahead,newblank,blank);

				}//end if newf=root f
				 else //the cost is higher - need to add it to the open list
				 {
					 if (newindex==-1)
					 {

						 ////TODO -WO lookahead
						 
						//if (LimitedLookAhead(stateIndex,newg,newh,old[stateIndex].g+old[stateIndex].h+lookahead,newblank)==100) 
						if(true)
						 {
								printf("%s\n","returning 100");
								return 100;
						}
						//LimitedLookAhead(stateIndex,newg,newh,old[stateIndex].g+old[stateIndex].h+lookahead,newblank);
						 if(newg+newh+lookahead<UpperLimit)
						{
							InsertHash(stateIndex,hashval,newblank,newg,newh);
						}
					}
					 else
					 {
						// if(test) printf("%s\n","duplicate b");
						 duplicatCounter++;
						 if (old[newindex].g>newg)
						{
						//	if(test) printf("%s\n","updating");
						//	if(CaseCouter==4 )
						//	{
						//solution=fopen("solution_41.txt","a");
						//fprintf(solution,"%s ","roc,");
						//for (int i=0;i<BOARDSIZE;i++)
						// fprintf(solution,"%d ",old[stateIndex].boardState[i]);
						// fprintf(solution,",%d,%d,%d,%d,%d\n",newg,newh,stateIndex,newf,lookahead);
						//fclose(solution);
						//	}
							/*printf("%s","Already exists in close list bb: ");
							for(int q=0;q<BOARDSIZE;q++)
								printf("%d ",old[stateIndex].boardState[q]);

							printf("%d ",newf);
							printf("%d ",old[newindex].g+old[newindex].h);
							printf("%d ",newg);
							printf("%d ",old[newindex].g);
							printf("%s\n","");
							string mystr;
							getline (cin,mystr);*/
							//printf("%s\n","deleting from IExpand after");
							if(old[newindex].heaplink==-1)
							{
									//printf("%s","array in close (newf>f): ");
									//for (int i=0;i<SIZE;i++)
									//	printf("%d ",old[newindex].boardState[i]);
									//printf("%s\n","");
									//printf("%s %d %s %d\n","the index is: ",newindex," OpenStart is: ", OpenStart);
									//printf("%s","array in check: ");
									//for (int i=0;i<SIZE;i++)
									//	printf("%d ",old[stateIndex].boardState[i]);
									//printf("%s\n","");
									//printf("%s %d %s %d\n","old f=",old[newindex].h+old[newindex].g," newf=",newf);
									//string mystr;
							  //       getline (cin,mystr);
								reopened++;
							}
							DeleteFromOpenList(newindex);
							//old[newindex].g=newg;
							//old[newindex].h=newh;
							
							//if(LimitedLookAhead(stateIndex,newg,newh,old[stateIndex].g+old[stateIndex].h+lookahead,newblank)==100) 
							if(true)
							{
								printf("%s\n","returning 100");
								return 100;
							}
							//LimitedLookAhead(stateIndex,newg,newh,old[stateIndex].g+old[stateIndex].h+lookahead,newblank);
							if(newg+newh+lookahead<UpperLimit)
							{
								InsertHash(stateIndex,hashval,newblank,newg,newh);
							}
						}
					 }

				 }
		
			}
			//printf("%s","Changing back: ");
			//for(int c=0;c<SIZE;c++)
			//	printf("%d ",old[stateIndex].boardState[c]);
			//printf("%s\n","");
			MakeMove(stateIndex,newblank);
			//printf("%s","To: ");
			//for(int c=0;c<SIZE;c++)
			//	printf("%d ",old[stateIndex].boardState[c]);
			//printf("%s\n","");
			//string mystr;
			//getline (cin,mystr);
							
	 //}//end if
	}//end for
		return 0;
}//end procedure


int IIExpandNode(int stateIndex,int g,int h,int lookahead, int PrevMove)
{
	int newblank;
	int newindex;
	int opindex;

	int newg;
	int newh;
	int newf;
	int flag=-1;

	int hashval;

	for (opindex = 0; opindex < SIZE; opindex++)
	{
		if (!OperMat[PrevMove][opindex])// 0 -> 4 -> 8
		 {
			 //printf("%s %d\n","not allowed move: ",opindex);
			continue;
		}

		newblank=opindex;
		MakeMove(stateIndex,opindex);
		newh=GetHuristicRegular(stateIndex,0);

		 newg=g+1;

		 newf=newh+newg;
		 //printf("%s\n","Array after the change:");
		 //for(int i=0;i<SIZE;i++)
			// printf("%d ",old[stateIndex].boardState[i]);
		 //printf("%s %d %s %d\n","g=",newg,"h=",newh);

		 if(abs(newh-h)!=1)
		 {
			 //printf("%s","inconsistent--->");
			 //printf("%s %d %s %d %s %d %s %d\n","old h=",h," old g=",g," new h=",newh," new g=",newg);
			 //string mystr;
			 // getline (cin,mystr);

		 }
		 if(newf<UpperLimit)
		 {


				//check if the changed node is a goal
				if(newh==0 && IsGoal(stateIndex))
				{
					//TODO-debug printing
					printf("%s\n","found a goal");
					printf("%s","f=");
					printf("%d\n",newf);
					printf("%s\n","");
					printf("%s","g=");
					printf("%d\n",newg);
					printf("%s\n","");
					printf("%s","The goal state is: ");
					for (int b=0;b<SIZE;b++)
						printf("%d ",old[stateIndex].boardState[b]);
					printf("%s\n","");


					UpperLimit=newf;
					goalDepth=newf;
				}

				//Calc hash and check if already exists
				hashval=CalcHash(old[stateIndex].boardState);
				newindex=SearchHash(old[stateIndex].boardState,hashval);
				if(newindex==stateIndex) newindex=-1;

				//if the current child has cost which is equal or less than the root cost -> add it to the close list and continue developing its children
				if(newf<=old[stateIndex].g+old[stateIndex].h)
				{
						if(newindex==-1)
						{
							Add2Close(stateIndex, hashval,newblank,newg,newh);
							flag=0;
						
						}//end if newindex
						else
						{
						
							duplicatCounter++;
							if (old[newindex].g>newg)
							{
		
								if(old[newindex].heaplink==-1)
								{

									reopened++;
								}
								DeleteFromOpenList(newindex);
								old[newindex].g=newg;
								old[newindex].h=newh;
								
								flag=0;

								
							}


						}
						if(flag==0)
						{
							 
							if(IIExpandNode(stateIndex,newg,newh,lookahead,newblank)==100) return 100;
						}

				}//end if newf=root f
				 else //the cost is higher - need to add it to the open list
				 {
					 if(newindex!=-1)
					 {
						 duplicatCounter++;
						 if (old[newindex].g>newg)
						 {
							 flag=0;
							if(old[newindex].heaplink==-1) reopened++;
							DeleteFromOpenList(newindex);
							old[newindex].g=newg;
							old[newindex].h=newh;
						 }

					 }
					 else
					 {
						 flag=0;
					 }
					 if(flag==0)
					 {
						 if(lookahead>0 && (newf-(old[stateIndex].g+old[stateIndex].h+lookahead)<=0))
						 {
							 printf("%s","Array for lookahead: ");
							 for(int i=0;i<SIZE;i++)
								 printf("%d ",old[stateIndex].boardState[i]);
							 printf("%s %d %s %d\n","  h=",newh," g=",newg);
							 //if(LimitedLookAhead(stateIndex,newg,newh,old[stateIndex].g+old[stateIndex].h+lookahead,newblank)==100) 
							if(true)
							 {
									printf("%s\n","returning 100");
									return 100;
							}
							 else
							 {
								// printf("%s %d\n","got delta value -->>",delta);
								 newh=newh+delta;
							 }
						 }
						 else
						 {
							 if (lookahead>0 && (newf-(old[stateIndex].g+old[stateIndex].h+lookahead)>0))
							 {
								 printf("%s %d %s %d\n","newf=", newf, " lookahead=",old[stateIndex].g+old[stateIndex].h+lookahead);
							 }
						 }
						
						 if(newg+newh+lookahead<UpperLimit)
						{
							printf("%s\n","inserting new state");
							InsertHash(stateIndex,hashval,newblank,newg,newh);
						}

					 }

					 }

				 }
				 MakeMove(stateIndex,newblank);
		
			}//end for
		return 0;
}//end procedure

//---------------------------------------------------------------------
//---------------------------------------------------------------------

void ReOpen(int stateIndex, int newg, int PrevMove)
{
	int ReArIndex=-1;

	old[stateIndex].g=newg;
	old[stateIndex].PrevMove=PrevMove;
	ReArIndex=old[stateIndex].heaplink;

	//printf("%s\n","Heap Before:");
	//	for (int i=0;i<OpenStart;i++)
	//{
	//	printf("%d %s %d %s",old[heap[i]].g+old[heap[i]].h,"->",old[heap[i]].g,";");
	//}
	// printf("%s\n","");
	if (old[stateIndex].heaplink==-1)
	{
		opened++;
		 copen++;
		 closed--;

		if(maxopen<copen) maxopen=copen;
		OpenStart++;
		ReArIndex=OpenStart;
		heap[OpenStart]=stateIndex;
		old[stateIndex].heaplink=OpenStart;
	}
	Heapify_up(ReArIndex);
	//for (int i=0;i<OpenStart;i++)
	//{
	//	printf("%d %s %d %s",old[heap[i]].g+old[heap[i]].h,"->",old[heap[i]].g,";");
	//}
	// printf("%s\n","");
 //	 string mystr;
	// getline (cin,mystr);


}


void FReOpen(int stateIndex, int newg, int PrevMove)
{
	int ReArIndex=-1;

	old[stateIndex].g=newg;
	old[stateIndex].PrevMove=PrevMove;
	ReArIndex=old[stateIndex].heaplink;

	if(stateIndex==137) printf("%s\n","reopen 137");
	//printf("%s\n","Heap Before:");
	//	for (int i=0;i<OpenStart;i++)
	//{
	//	printf("%d %s %d %s",old[heap[i]].g+old[heap[i]].h,"->",old[heap[i]].g,";");
	//}
	// printf("%s\n","");
	if (old[stateIndex].heaplink==-1)
	{
		opened++;
		 copen++;
		 closed--;

		if(maxopen<copen) maxopen=copen;
		OpenStart++;
		ReArIndex=OpenStart;
		heap[OpenStart]=stateIndex;
		old[stateIndex].heaplink=OpenStart;
	}
	//FHeapify_up(ReArIndex);
	FHeapify_up(ReArIndex);
	//for (int i=0;i<OpenStart;i++)
	//{
	//	printf("%d %s %d %s",old[heap[i]].g+old[heap[i]].h,"->",old[heap[i]].g,";");
	//}
	// printf("%s\n","");
 //	 string mystr;
	// getline (cin,mystr);


}


int ClassicExpandNode(int stateIndex, int g, int h, int PrevMove)
{
	int hash;
	int newindex;
	int newh;
	int newg;


	if(IsGoal(stateIndex))
	{
		goalDepth=old[stateIndex].g;
		return 100;

	}
	for (int newMove = 0; newMove < SIZE; newMove++)
	{
		if (!OperMat[PrevMove][newMove])
		 {
			 //printf("%s %d\n","not allowed move: ",opindex);
			continue;
		}

		//else - generate the potential child by modifying the child
		MakeMove(stateIndex,newMove);

		hash=CalcHash(old[stateIndex].boardState);
		newindex=SearchHash(old[stateIndex].boardState,hash);
		if(newindex==stateIndex) newindex=-1;

		newg=g+1;
        //ConvertStateToDual(stateIndex);
		//newh=GetHuristicRegular(DualState);
		newh=GetHuristicRegular(stateIndex,0);
		newh=MAX(h-1,newh);
		// if the child is unique - add it to the OPEN list
		
		if(newindex==-1)
		{
			InsertHash(stateIndex,hash,newMove,newg,newh);	
		}
		else
		{
			if(newg<old[newindex].g)
			{
				if(old[newindex].h!=newh) old[newindex].h=newh;
				ReOpen(newindex,newg,newMove);				
			}
		}
		MakeMove(stateIndex,newMove);
	}

	return -1;
}


int FLimitedLookAhead(int stateIndex,int g, int h,int lookahead, int PrevMove)
{
	int newg;
	int newh;
	int newf;
	int returnF;

	int result=0;
	returnF=10000;
	//if(IsGoal(stateIndex))
	//{
	//	if(g<UpperLimit) UpperLimit=g;
	//	printf("%s %d\n","---is a goal---",UpperLimit);

	//	//string mystr;
	//	//getline (cin,mystr);
	//	return g+h;
	//}

	if(g+h>lookahead)
	{
		//printf("%s %d\n","lookahead exceeded -",g+h);

		//string mystr;
		//getline (cin,mystr);
		return g+h;
	}

	if(IsGoal(stateIndex))
	{
		if(g<UpperLimit) UpperLimit=g;
		printf("%s %d\n","---is a goal---",UpperLimit);

		//string mystr;
		//getline (cin,mystr);
		return g+h;
	}
	//solution=fopen("LH_1.txt","a");
	//fprintf(solution,"%s ","lh,");
	//	for (int j=0;j<SIZE;j++)
	//		fprintf(solution,"%d ",old[stateIndex].boardState[j]);
	//		fprintf(solution,",%d,%d,%d,\n",g,h,lookahead);
	//	fclose(solution);
	//if(g+h>lookahead) return 100;
	newg=g+1;

	for (int newMove = 0; newMove < SIZE; newMove++)
	{
		if (!OperMat[PrevMove][newMove])
		 {
			 //printf("%s %d\n","not allowed move: ",opindex);
			continue;
		}

		//else - generate the potential child by modifying the child
		MakeMove(stateIndex,newMove);
        //ConvertStateToDual(stateIndex);
		newh=GetHuristicRegular(stateIndex,0);
		//if(h-newh>1) printf("%s %d %s %d\n","h=",h,"newh=",newh);
		
		newh=MAX(h-1,newh);
		ImmediateGenerated++;
		newf=newh+newg;
		//printf("%s %d %s %d %s %d %s %d %s %d %s %d\n","childg=", newg,"childh=",newh,"parenth=",h,"parentf=",h+g, "childf=",newg+newh,"lookahead=",lookahead);
		//if(IsGoal(stateIndex))
		//{
		//	if(newg<UpperLimit) UpperLimit=newg;
		//	//printf("%s %d %s %d %s %d\n","goal found in depth - ",newg," pcost=",old[stateIndex].cost," move=",newMove);
		//	//printf("%s %d %s %d %s %d %s %d %s %d %s %d\n","childg=", newg,"childh=",newh,"parenth=",h,"parentf=",h+g, "childf=",newg+newh,"lookahead=",lookahead);
		//	//MakeMove(stateIndex,newMove);
		//	//return -2;
		//	//printf("%s %d %s %d %s %d\n","stateIndex=",stateIndex," IPF=",h+g," OrPF=",old[stateIndex].g+old[stateIndex].h);
		//	//string mystr;
		//	//getline (cin,mystr);

		//}

		
		//solution=fopen("LH_1.txt","a");
		//fprintf(solution,"%s ","lhc,");
		//for (int j=0;j<SIZE;j++)
		//	fprintf(solution,"%d ",old[stateIndex].boardState[j]);
		//	fprintf(solution,",%d,%d,%d,\n",newg,newh,lookahead);
		//fclose(solution);
			if(newf<UpperLimit)
			{
				//printf("%s %d %s %d %s %d %s %d\n","f=",h+g,"newf=",newf,"newg=",newg,"lookahead=",lookahead);
				//printf("%s %d %s %d %s %d %s %d %s %d %s %d\n","childg=", newg,"childh=",newh,"parenth=",h,"parentf=",h+g, "childf=",newg+newh,"lookahead=",lookahead);
				result=FLimitedLookAhead(stateIndex,newg,newh,lookahead,newMove);
			}
			returnF=MIN(returnF,result);
		MakeMove(stateIndex,newMove);
		//if(result==100) return 100;

	}
	return returnF;
}

int FIDAStar(int stateIndex,int g, int h,int lookahead,int PrevMove)
{
	int newg;
	int newh;
	int newf,hash,newindex,breakMove;

	bool breakTest=false;
	breakMove=-1;

	newg=g+1;
	for (int newMove=0;newMove<SIZE;newMove++)
	{
		if (!OperMat[PrevMove][newMove]) // Illegal move
			continue;

		MakeMove(stateIndex,newMove);
		ImmediateGenerated++;
		newh=GetHuristicRegular(stateIndex,0);

		newh=MAX(newh,h-1);
		newf=newg+newh;

		if(IsGoal(stateIndex))//&& newf<=lookahead) 
		{
			if(newg<UpperLimit) 
				UpperLimit=newg;
			if (DEBUG_PRINTS)
				printf("%s %d %s %d %s %d %s %d %s %d\n","found goal in",UpperLimit,"parentf=",old[stateIndex].h+old[stateIndex].g,"pcost=",old[stateIndex].cost,"lookahead=",lookahead,"stateIndex=",stateIndex);

			MakeMove(stateIndex,newMove);
			continue;
			//QA - maybe I need to return 
			//[ANSWER: In a domain with non-uniform edge cost you need to continue]
		}

		// Continue DFS recursion if limit has not been reached yet
		if(newf<=lookahead && newf<UpperLimit )//&& lookahead<UpperLimit)
		{
			FIDAStar(stateIndex,newg,newh,lookahead,newMove);
		}
		else
		{		
			if (newf<minf) 
				minf=newf;
		}

		MakeMove(stateIndex,newMove);
	}

	return -1;
}
int FLimitedLookAhead1(int stateIndex,int g, int h,int lookahead, int PrevMove)
{
	int newg;
	int newh;
	int newf;
	int returnF;
	FILE *solution;

	int result=0;
	returnF=10000;
	newg=g+1;

	//printf("%s %d %s %d %s %d\n","g=",g,"h=",h,"lookahead=",lookahead);
	for (int newMove = 0; newMove < SIZE; newMove++)
	{
		if (!OperMat[PrevMove][newMove])
		 {
			// printf("%s %d %s %d\n","not allowed move: ",newMove,"g=",newg);
			continue;
		}

		//else - generate the potential child by modifying the child
		MakeMove(stateIndex,newMove);

		newh=GetHuristicRegular(stateIndex,0);
				if(IsGoal(stateIndex))
			{
				printf("%s %d\n","goal in depth: ",newg);
				if(newg<UpperLimit) UpperLimit=newg;
			}
		
		newh=MAX(h-1,newh);
		ImmediateGenerated++;
		newf=newh+newg;
		if(newf==old[stateIndex].h+old[stateIndex].g) sameV++;

		//printf("%s %d %s %d %s %d\n","f=",h+g,"newf=",newf,"lookahead=",lookahead);
	//	printf("%s %d %s %d %s %d %s %d %s %d %s %d %s %d\n","childg=", newg,"childh=",newh,"parentg=",g,"parenth=",h, "childf=",newg+newh,"lookahead=",lookahead,"returnF=",returnF);
		//if(newf>lookahead)
		//{
		//	returnF=MIN(returnF,newf);
		//}
		if(newf<UpperLimit && newf<=lookahead)
		{
			if(newf<returnF)
			{
	//			printf("%s\n","continue with this node");
				if(IsGoal(stateIndex))
				{
					//printf("%s %d\n","goal in depth: ",newg);
					if(newg<UpperLimit) UpperLimit=newg;
				}
				else
				{
					int returnFF=FLimitedLookAhead1(stateIndex,newg,newh,lookahead,newMove);
				
	//				printf("%s %d %s %d\n","returnF=",returnF,"returnFF=",returnFF);
					if(returnFF<returnF) returnF=returnFF;
					if(returnF==lookahead+1)
					{
						
	//					printf("%s\n","returning F");
						return returnF;
					}
	//				printf("%s %d %s %d\n","The new min is",returnFF," the current min=",returnF);
					//string mystr;
					//getline (cin,mystr);
				}
			}
			else
			{
				printf("%s\n","what should I do with this node?");
			}
				

		}
				//printf("%s %d %s %d %s %d %s %d\n","f=",h+g,"newf=",newf,"newg=",newg,"lookahead=",lookahead);
				//printf("%s %d %s %d %s %d %s %d %s %d %s %d\n","childg=", newg,"childh=",newh,"parenth=",h,"parentf=",h+g, "childf=",newg+newh,"lookahead=",lookahead);
	
			MakeMove(stateIndex,newMove);
		//printf("%s %d\n","returnF=",returnF);
		
		if(newg+newh>lookahead)
		{

			if (newg+newh-lookahead==1)
			{

	//			printf("%s %d %s %d %s %d\n","min returned-->> lookahead=",lookahead,"newf=",newf,"returnF=",returnF);
	//			string mystr;
	//			getline (cin,mystr);
				returnF=newf;
				//continue;
				return returnF;
			}
	//		printf("%s %d %s %d\n","returnF=",returnF," newf=",newf);
			returnF=MIN(returnF,newf);
	//		string mystr;
	//		getline (cin,mystr);

			//if(old[stateIndex].g+1-newg>1)
			//return g+h;
			//else
			// returnF=MIN(newf,returnF);
		}
		//if(result==100) return 100;

	}
	//printf("%s %d\n","returnF=",returnF);
	//string mystr;
	//getline (cin,mystr);

	return returnF;
}

int GLimitedLookAhead1(int stateIndex,int g, int h,int lookahead, int PrevMove)
{
	int newg;
	int newh;
	int newf;
	int returnF;
	FILE *solution;

	int result=0;
	returnF=10000;
	newg=g+1;

	for (int newMove = 0; newMove < SIZE; newMove++)
	{
		if (!OperMat[PrevMove][newMove])
		 {
			// printf("%s %d %s %d\n","not allowed move: ",newMove,"g=",newg);
			continue;
		}

		//else - generate the potential child by modifying the child
		MakeMove(stateIndex,newMove);

		newh=GetHuristicRegular(stateIndex,0);
	
		newh=MAX(h-1,newh);
		ImmediateGenerated++;
		newf=newh+newg;
		if(newf==old[stateIndex].h+old[stateIndex].g) sameV++;
		if(IsGoal(stateIndex))
		{
				//printf("%s %d\n","goal in depth: ",newg);
				if(newg<UpperLimit) UpperLimit=newg;
				//string mystr;
				//getline (cin,mystr);
				//MakeMove(stateIndex,newMove);
				//return 10000;
		}
		//printf("%s %d %s %d %s %d %s %d %s %d %s %d\n","childg=", newg,"childh=",newh,"parenth=",h,"parentf=",h+g, "childf=",newg+newh,"lookahead=",lookahead);

		//if(newg>lookahead) printf("%s %d %s %d\n","lookahead=",lookahead,"newg=",newg);
		//if(newf==old[stateIndex].h+old[stateIndex].g) lookahead++;
		if( newf<UpperLimit && newg<lookahead)
		{
			//if(IsGoal(stateIndex))
			//{
			//	//printf("%s %d\n","goal in depth: ",newg);
			//	if(newg<UpperLimit) UpperLimit=newg;
			//}
			//else
			//{
				int returnFF=GLimitedLookAhead1(stateIndex,newg,newh,lookahead,newMove);
				//printf("%s %d\n","returned returnF=",returnFF);
				if (returnFF<returnF) returnF=returnFF;
				//returnF=MIN(returnF,newf)
			//}
				//printf("%s %d %s %d %s %d %s %d\n","f=",h+g,"newf=",newf,"newg=",newg,"lookahead=",lookahead);
				//printf("%s %d %s %d %s %d %s %d %s %d %s %d\n","childg=", newg,"childh=",newh,"parenth=",h,"parentf=",h+g, "childf=",newg+newh,"lookahead=",lookahead);
		}
		MakeMove(stateIndex,newMove);
		if(newg==lookahead)
		{
			//printf("%s %d %s %d %s %d\n","returnF=",returnF," newf=",newf," newg=",newg);
			returnF=MIN(returnF,newf);
			//return returnF;
			//return newf;
		}
			
		//printf("%s %d\n","returnF=",returnF);
		
		//if(result==100) return 100;

	}
	//printf("%s %d\n","returnF=",returnF);
	//string mystr;
	//getline (cin,mystr);

	return returnF;
}


int FExpandNode(int stateIndex, int g, int h, int PrevMove,int lookahead)
{
	int hash;
	int newindex;
	int newh;
	int newg;
	int newcost;
	FILE *solution;
	int LHResult;


	LHResult=-1;
	newcost=1000;
	if(IsGoal(stateIndex))
	{
		//printf("%s\n","found goal");
		//for(int i=0;i<SIZE;i++)
		//	printf("%d ",old[stateIndex].boardState[i]);
		//printf("%s\n","");
		if(old[stateIndex].g<UpperLimit) UpperLimit=old[stateIndex].g;
		printf("%s %d\n","found goal-->>",UpperLimit);
		//goalDepth=old[stateIndex].g;
		return 100;

	}
	for (int newMove = 0; newMove < SIZE; newMove++)
	{
		if (!OperMat[PrevMove][newMove])
		 {
			 //printf("%s %d\n","not allowed move: ",opindex);
			continue;
		}

		//else - generate the potential child by modifying the child
		MakeMove(stateIndex,newMove);

		hash=CalcHash(old[stateIndex].boardState);
		newindex=SearchHash(old[stateIndex].boardState,hash);
		if(newindex==stateIndex) newindex=-1;

		newg=g+1;
        //ConvertStateToDual(stateIndex);
		//newh=GetHuristicRegular(DualState);
		newh=GetHuristicRegular(stateIndex,0);
		newh=MAX(h-1,newh);
		
		//if(newg+newh<=lookahead)
		//{
		//	LHResult=FLimitedLookAhead(stateIndex,newg,newh,lookahead,newMove);
		//	newcost=LHResult;
		//}
		//else
		//{
		//	newcost=newg+newh;
		//}
		if(newg+newh<=old[stateIndex].cost) newcost=old[stateIndex].cost;
		else
			newcost=newg+newh;
		// if the child is unique - add it to the OPEN list
		
		if(newindex==-1)
		{
			if(newcost<UpperLimit)
			{
				//printf("%s %d %s %d\n","Adding - cost=",newcost," f=",newg+newh);
			FInsertHash(stateIndex,hash,newMove,newg,newh,newcost);	
			}
		}
		else
		{
			if(newg<old[newindex].g)
			{
				if(old[newindex].heaplink==-1)
				{
					if(newcost<UpperLimit)
					{
					old[newindex].g=-1;
					old[newindex].h=-1;
					old[newindex].cost=0;
					for (int i=0;i<SIZE;i++)
						old[newindex].boardState[i]=-1;
					
					FInsertHash(stateIndex,hash,newMove,newg,newh,newcost);
					}
				}
				else
				{
					if(newcost<UpperLimit)
					{
					if(old[newindex].h!=newh) old[newindex].h=newh;
					if(old[newindex].cost!=newcost) old[newindex].cost=newcost;
					ReOpen(newindex,newg,newMove);
					}
				}
			}
		}
		MakeMove(stateIndex,newMove);
	}

	return -1;
}

int CExpandNode1(int stateIndex, int g, int h, int PrevMove)
{
	int hash;
	int newindex;
	int newh;
	int newg;
	int newcost;
	FILE *solution;
	int LHResult;


//	printf("%s\n","---------------- Expand -------------");
	LHResult=-1;
	newcost=1000;
	if(IsGoal(stateIndex))
	{
		if(old[stateIndex].g<UpperLimit) UpperLimit=old[stateIndex].g;
		return 100;
	}
	for (int newMove = 0; newMove < SIZE; newMove++)
	{
		if (!OperMat[PrevMove][newMove])
		 {
			 //printf("%s %d\n","not allowed move: ",opindex);
			continue;
		}

		//else - generate the potential child by modifying the child
		MakeMove(stateIndex,newMove);
		//if(IsGoal(stateIndex))
		//{
		////printf("%s\n","found goal");
		////for(int i=0;i<SIZE;i++)
		////	printf("%d ",old[stateIndex].boardState[i]);
		////printf("%s\n","");
		//	if(newg<UpperLimit) UpperLimit=newg;
		////printf("%s %d\n","found goal-->>",UpperLimit);
		////goalDepth=old[stateIndex].g;

		//}

		hash=CalcHash(old[stateIndex].boardState);
		newindex=SearchHash(old[stateIndex].boardState,hash);
		if(newindex==stateIndex) newindex=-1;
		newcost=1000;
		newg=g+1;
        //ConvertStateToDual(stateIndex);
		//newh=GetHuristicRegular(DualState);
		newh=GetHuristicRegular(stateIndex,0);
		if(h-1>newh) sameV++;
		newh=MAX(h-1,newh);
		int newf=newh+newg;
		
		if(newindex==-1)
		{
			if(newf<UpperLimit)
			{
			//printf("%s %d %s %d %s %d %s %d\n","Adding - cost=",newcost," f=",newg+newh,"lookahead=",lookahead,"parentf=",g+h);
			InsertHash(stateIndex,hash,newMove,newg,newh);	
			}
		}
		else
		{
			if(newg<old[newindex].g)
			{
				if(old[newindex].heaplink==-1)
				{
					if(newf<UpperLimit)
					{
						reclose++;
					old[newindex].g=-1;
					old[newindex].h=-1;
					old[newindex].cost=0;
					for (int i=0;i<SIZE;i++)
						old[newindex].boardState[i]=-1;
					//printf("%s %d %s %d %s %d %s %d\n","Reclose - cost=",newcost," f=",newg+newh,"lookahead=",lookahead,"parenth=",g+h);
					InsertHash(stateIndex,hash,newMove,newg,newh);
					}
				}
				else
				{
					if(newf<UpperLimit)
					{
					//	printf("%s\n","~~~~~~~~~~~~~~~~~~~ ReOpening ~~~~~~~~~~~~~~~~~");
						//string mystr1;
						//getline (cin,mystr1);
					reopened++;
					if(old[newindex].h!=newh) old[newindex].h=newh;
					//if(old[newindex].cost!=newcost) old[newindex].cost=newcost;
					ReOpen(newindex,newg,newMove);
					}
				}
			}
		}
		//}
		//}
		MakeMove(stateIndex,newMove);
	}
	//string mystr1;
	//getline (cin,mystr1);
	return -1;
}


int FExpandNode1(int stateIndex, int g, int h, int PrevMove,int lookahead)
{
	int hash;
	int newindex;
	int newh;
	int newg;
	int newcost;
	FILE *solution;
	int LHResult;

	LHResult=-1;
	newcost=1000;
	if(IsGoal(stateIndex))
	{
		if(g<UpperLimit) UpperLimit=g;
		return 100;
	}
	newg=g+1;
	for(int newMove=0;newMove<SIZE;newMove++)
	{
		if (!OperMat[PrevMove][newMove]) continue;

		//else - generate the potential child by modifying the child
		MakeMove(stateIndex,newMove);
		if(IsGoal(stateIndex))
			if(newg<UpperLimit) 
				UpperLimit=newg;

		hash=CalcHash(old[stateIndex].boardState);
		newindex=SearchHash(old[stateIndex].boardState,hash);
		if(newindex==stateIndex) newindex=-1;
		newcost=1000;
		newh=GetHuristicRegular(stateIndex,0);
		newh=MAX(h-1,newh);

		if(newh+newg<UpperLimit)
		{
		if(newg+newh<=NextBestF) //need to add to CLOSE
		{
			int IEstate=-1;
			bool IEflag=false;
			int IEg=newg;
			if(newindex==-1)//If this is a new node - add to CLOSE
			{
				//newcost=FIDAStar(stateIndex,newg,newh,lookahead,newMove);
				int cindex=FAdd2Close(stateIndex,hash,newMove,newg,newh,bestc);
				//IEstate=cindex;
				IEstate=stateIndex;
				IEflag=true;
				//perform the IIIExpand
			}
			else//the node is already in memory
			{
				if(old[newindex].heaplink==-1)//if the node is in CLOSE
				{
					//printf("%s %d %s %d %s %d %s %d %s %d %s %d %s %d %s %d\n","in close - g=",old[newindex].g,"h=",old[newindex].h,"cost=",old[newindex].cost,"index=",newindex,"new - g=",newg,"h=",newh,"cost=",old[stateIndex].cost,"index=",stateIndex);
					//string mystr1;
					//getline (cin,mystr1);
					if(old[newindex].g>newg)
					{
						old[newindex].h=newh;
						//if (old[newindex].g<newg) IEg=old[stateIndex].g;
						old[newindex].cost=old[stateIndex].cost;
						IEstate=stateIndex;//newindex
						IEflag=true;
						//perform the IIIExpand
					}
				}
				else //the node is in OPEN
				{
					//printf("%s %d %s %d %s %d %s %d %s %d %s %d\n","in open - g=",old[newindex].g,"h=",old[newindex].h,"cost=",old[newindex].cost,"new - g=",newg,"h=",newh,"cost=",old[stateIndex].cost);
					//string mystr1;
					//getline (cin,mystr1);
					if(old[newindex].g>newg)
					{
						//Need to delete it from the OPEN
						DeleteFromOpenList(newindex);
						for(int i=0;i<SIZE;i++)
							old[newindex].boardState[i]=-1;
						old[newindex].g=-1;
						old[newindex].h=-1;
						old[newindex].cost=-1;
						IEstate=stateIndex;
						FAdd2Close(stateIndex,hash,newMove,newg,newh,bestc);
						//old[newindex].h=newh;
						//old[newindex].g=newg;
						//old[newindex].PrevMove=newMove;
						//if(old[newindex].cost>newg+newh) old[newindex].cost=old[stateIndex].cost;
						//IEstate=newindex;
						IEflag=true;
					}//end if
					
				}//end else node in OPEN
			}//end else node in memory
		
			//Immediate Generate nodes based on flags
			if(IEflag==true)
			{
				//printf("%s\n","IE");
				//printf("%s","before:");
				//for (int i=0;i<SIZE;i++)
				//	printf("%d ",old[IEstate].boardState[i]);
				//printf("%s\n","");

				IE++;
				FExpandNode1(IEstate,newg,newh,newMove,lookahead);
				//printf("%s","after :");
				//for (int i=0;i<SIZE;i++)
				//	printf("%d ",old[IEstate].boardState[i]);
				//printf("%s\n","");
			}
			
		}
		else
		{
		int ActualLH;
		if(bestc<=lookahead) ActualLH=MIN(NextBestC,lookahead);
		else
			ActualLH=-1;
		//ActualLH=MIN(NextBestC,lookahead);
		//printf("%s %d %s %d %s %d %s %d\n","NextBestC=",NextBestC,"lookahead=",lookahead,"ActualLH=",ActualLH,"childf=",newh+newg);
		if(newg+newh<=ActualLH )
		{
			
			//printf("%s\n","performing LH");
			//printf("%s %d %s %d %s %d %s %d\n","performing LH, g=",newg,"h=",newh,"ActualLH=",ActualLH,"lookahead=",lookahead);
			//string mystr2;
			//getline (cin,mystr2);
			minf=10000;
			int tempLH=newg+newh;
			//printf("%s %d %s %d\n","ActualLH=",ActualLH,"tempLH=",tempLH);
			while(tempLH<=ActualLH && tempLH<UpperLimit)
			{
				//printf("%s\n","in while loop");
				FIDAStar(stateIndex,newg,newh,tempLH,newMove);
				//printf("%s %d\n","minf=",minf);
				tempLH=minf;
				//printf("%s %d %s %d\n","f=",newg+newh,"LH=",tempLH);
				minf=100000;
			}
			//newcost=minf;
			LHFrom++;
			newcost=tempLH;
			//printf("%s %d %s %d %s %d\n","newcost=",newcost,"f=",newg+newh,"lookahead=",lookahead);
			//string mystr1;
			//getline (cin,mystr1);
			if(CostArr[newcost]==-1) CostArr[newcost]=1;
			
			
		}
		else
		{
			newcost=newg+newh;
			//printf("%s\n","f bigger than lookahead, no LH required");
		}
		//printf("%s %d %s %d %s %d\n","--<< childh=",newh,"childg=",newg,"childcost=",newcost);
		//	string mystr1;
			//getline (cin,mystr1);
		// if the child is unique - add it to the OPEN list
		
		if(newindex==-1)
		{
			if(newcost<UpperLimit)
			{
			//printf("%s %d %s %d %s %d %s %d\n","Adding - cost=",newcost," f=",newg+newh,"lookahead=",lookahead,"parentf=",g+h);
			FInsertHash(stateIndex,hash,newMove,newg,newh,newcost);	
			}
		}
		else
		{
			if(newg<old[newindex].g)
			{
				if(old[newindex].heaplink==-1)
				{
					if(newcost<UpperLimit)
					{
						reopened++;
					FoundInC++;
					old[newindex].g=-1;
					old[newindex].h=-1;
					old[newindex].cost=0;
					for (int i=0;i<SIZE;i++)
						old[newindex].boardState[i]=-1;
					//printf("%s %d %s %d %s %d %s %d\n","Reclose - cost=",newcost," f=",newg+newh,"lookahead=",lookahead,"parenth=",g+h);
					FInsertHash(stateIndex,hash,newMove,newg,newh,newcost);
					}
				}
				else
				{
					if(newcost<UpperLimit)
					{
						reopened++;
					FoundInO++;
					//	printf("%s\n","~~~~~~~~~~~~~~~~~~~ ReOpening ~~~~~~~~~~~~~~~~~");
						//string mystr1;
						//getline (cin,mystr1);

					if(old[newindex].h!=newh) old[newindex].h=newh;
					if(old[newindex].cost!=newcost) old[newindex].cost=newcost;
					FReOpen(newindex,newg,newMove);
					}
				}
			}
		}
		}
		}
		MakeMove(stateIndex,newMove);
	}
	//string mystr1;
	//getline (cin,mystr1);
	return -1;
}



int FExpandNode2(int stateIndex, int g, int h, int PrevMove,int lookahead)
{
	int hash;
	int newindex;
	int newh;
	int newg;
	int newcost;
	FILE *solution;
	int LHResult;


	//printf("%s\n","---------------- Expand -------------");
	//printf("%s %d %s %d %s %d %s %d\n","cost=",old[stateIndex].cost,"lookahead=",lookahead,"g=",g,"h=",h);
	//string mystr11;
	//getline (cin,mystr11);
	LHResult=-1;
	newcost=1000;
	if(IsGoal(stateIndex))
	{
		printf("%s\n","found goal");
		//for(int i=0;i<SIZE;i++)
		//	printf("%d ",old[stateIndex].boardState[i]);
		//printf("%s\n","");
		if(g<UpperLimit) UpperLimit=g;
		printf("%s %d\n","found goal-->>",UpperLimit);
		//goalDepth=old[stateIndex].g;
		return 100;

	}
	newg=g+1;
	for (int newMove = 0; newMove < SIZE; newMove++)
	{
		if (!OperMat[PrevMove][newMove])
		 {
			 //printf("%s %d\n","not allowed move: ",opindex);
			continue;
		}

		//else - generate the potential child by modifying the child
		MakeMove(stateIndex,newMove);
		if(IsGoal(stateIndex))
		{
		//printf("%s\n","found goal");
		//for(int i=0;i<SIZE;i++)
		//	printf("%d ",old[stateIndex].boardState[i]);
		//printf("%s\n","");
			if(newg<UpperLimit) UpperLimit=newg;
			//if(lookahead>UpperLimit) lookahead=UpperLimit-1;
		printf("%s %d\n","found goal-->>",newg);
		//goalDepth=old[stateIndex].g;

		}

		hash=CalcHash(old[stateIndex].boardState);
		newindex=SearchHash(old[stateIndex].boardState,hash);
		if(newindex==stateIndex) newindex=-1;
		newcost=1000;
		newh=GetHuristicRegular(stateIndex,0);
		//printf("%s %d\n","newh=",newh);
		//string mystr11;
		//getline (cin,mystr11);
		newh=MAX(h-1,newh);
		//printf("%s %d %s %d\n","newf=",newg+newh,"bestc=",bestc);

		if(newh+newg<UpperLimit)
		{
		if(newg+newh<=NextBestF) //need to add to CLOSE
		{
			//printf("%s %d %s %d %s %d %s %d %s %d %s %d\n","IE - parentg=",g,"parenth=",h,"childg=",newg,"childh=",newh,"lookahead=",lookahead,"bestc=",bestc);
			//string mystr;
			//getline (cin,mystr);
			int IEstate=-1;
			bool IEflag=false;
			int IEg=newg;
			if(newindex==-1)//If this is a new node - add to CLOSE
			{
				//newcost=FIDAStar(stateIndex,newg,newh,lookahead,newMove);
				int cindex=FAdd2Close(stateIndex,hash,newMove,newg,newh,bestc);
				//IEstate=cindex;
				IEstate=stateIndex;
				IEflag=true;
				//perform the IIIExpand
			}
			else//the node is already in memory
			{
				if(old[newindex].heaplink==-1)//if the node is in CLOSE
				{
					//printf("%s %d %s %d %s %d %s %d %s %d %s %d %s %d %s %d\n","in close - g=",old[newindex].g,"h=",old[newindex].h,"cost=",old[newindex].cost,"index=",newindex,"new - g=",newg,"h=",newh,"cost=",old[stateIndex].cost,"index=",stateIndex);
					//string mystr1;
					//getline (cin,mystr1);
					if(old[newindex].g>newg)
					{
						old[newindex].h=newh;
						//if (old[newindex].g<newg) IEg=old[stateIndex].g;
						old[newindex].cost=old[stateIndex].cost;
						IEstate=stateIndex;//newindex
						IEflag=true;
						//perform the IIIExpand
					}
				}
				else //the node is in OPEN
				{
					//printf("%s %d %s %d %s %d %s %d %s %d %s %d\n","in open - g=",old[newindex].g,"h=",old[newindex].h,"cost=",old[newindex].cost,"new - g=",newg,"h=",newh,"cost=",old[stateIndex].cost);
					//string mystr1;
					//getline (cin,mystr1);
					if(old[newindex].g>newg)
					{
						//Need to delete it from the OPEN
						DeleteFromOpenList(newindex);
						for(int i=0;i<SIZE;i++)
							old[newindex].boardState[i]=-1;
						old[newindex].g=-1;
						old[newindex].h=-1;
						old[newindex].cost=-1;
						IEstate=stateIndex;
						FAdd2Close(stateIndex,hash,newMove,newg,newh,bestc);
						//old[newindex].h=newh;
						//old[newindex].g=newg;
						//old[newindex].PrevMove=newMove;
						//if(old[newindex].cost>newg+newh) old[newindex].cost=old[stateIndex].cost;
						//IEstate=newindex;
						IEflag=true;
					}//end if
					
				}//end else node in OPEN
			}//end else node in memory
		
			//Immediate Generate nodes based on flags
			if(IEflag==true)
			{
				//printf("%s\n","IE");
				//printf("%s","before:");
				//for (int i=0;i<SIZE;i++)
				//	printf("%d ",old[IEstate].boardState[i]);
				//printf("%s\n","");

				IE++;
				FExpandNode2(IEstate,newg,newh,newMove,lookahead);
				//printf("%s","after :");
				//for (int i=0;i<SIZE;i++)
				//	printf("%d ",old[IEstate].boardState[i]);
				//printf("%s\n","");
			}
			
		}
		else
		{
			if(newg+newh<bestc) newcost=bestc;
			else newcost=newg+newh;
		//if(newcost<=lookahead) FIDAStar(stateIndex,newg,newh,lookahead,PrevMove);
		if(newindex==-1)
		{
			if(newcost<UpperLimit)
			{
		//	printf("%s %d %s %d %s %d %s %d\n","Adding - cost=",newcost," f=",newg+newh,"lookahead=",lookahead,"bestc=",bestc);
			FInsertHash(stateIndex,hash,newMove,newg,newh,newcost);	
			}
		}
		else
		{
			if(newg<old[newindex].g)
			{
				if(old[newindex].heaplink==-1)
				{
					if(newcost<UpperLimit)
					{
						reclose++;
					old[newindex].g=-1;
					old[newindex].h=-1;
					old[newindex].cost=0;
					for (int i=0;i<SIZE;i++)
						old[newindex].boardState[i]=-1;
					//printf("%s %d %s %d %s %d %s %d\n","Reclose - cost=",newcost," f=",newg+newh,"lookahead=",lookahead,"parenth=",g+h);
					FInsertHash(stateIndex,hash,newMove,newg,newh,newcost);
					}
				}
				else
				{
					if(newcost<UpperLimit)
					{
					//	printf("%s\n","~~~~~~~~~~~~~~~~~~~ ReOpening ~~~~~~~~~~~~~~~~~");
						//string mystr1;
						//getline (cin,mystr1);
					reopened++;
					if(old[newindex].h!=newh) old[newindex].h=newh;
					if(old[newindex].cost!=newcost) old[newindex].cost=newcost;
					FReOpen(newindex,newg,newMove);
					}
				}
			}
		}
		}
		}
		MakeMove(stateIndex,newMove);
	}
	//string mystr1;
	//getline (cin,mystr1);
	return -1;
}


int GIDAStar(int stateIndex,int g, int h,int lookahead,int PrevMove)
{
	int newg, newh, newf,minf,hash,newindex,breakMove;

	bool breakTest=false;
	breakMove=-1;
	//printf("%s\n","in ida");

	minf=100000;
	newg=g+1;
	for (int newMove=0;newMove<SIZE;newMove++)
	{
		if (!OperMat[PrevMove][newMove])
		 {
			 //printf("%s %d %s %d\n","not allowed move: ",newMove,"minf=",minf);
			continue;
		}
		MakeMove(stateIndex,newMove);
		ImmediateGenerated++;
		newh=GetHuristicRegular(stateIndex,0);
		newh=MAX(newh,h-1);
		newf=newg+newh;
		if(newf==h+g) sameV++;
		//if(newf>minf)
		//printf("%s %d %s %d %s %d %s %d\n","newf=",newf,"oldf=",h+g,"minf=",minf,"lookahead=",lookahead);
		if(IsGoal(stateIndex) && newg<=lookahead)
		{
			if(newg<UpperLimit) UpperLimit=newg;
			MakeMove(stateIndex,newMove);
			continue;
			//QA - maybe I need to return
		}
		if(newg<lookahead && newf<UpperLimit && newf<minf)
		{
			int minff=GIDAStar(stateIndex,newg,newh,lookahead,newMove);
			if(minff<minf) minf=minff;
			//printf("%s %d\n","minf=",minf);
		}
		else
		{
			if (newf<minf) minf=newf;
			//if(minf==lookahead+1)
			//{
			//if(!breakTest)
			//{
			//	breakTest=true;
			//	lookahead--;
			//}
			//}
		}



	MakeMove(stateIndex,newMove);
	//if(breakTest) newMove=breakMove;
	}

	return minf;
}
int GExpandNode1(int stateIndex, int g, int h, int PrevMove,int lookahead)
{
	int hash;
	int newindex;
	int newh;
	int newg;
	int newcost;
	FILE *solution;
	int LHResult;


//	printf("%s\n","---------------- Expand -------------");
	LHResult=-1;
	newcost=1000;
	
	if(IsGoal(stateIndex))
	{
		printf("%s\n","found goal");
		//for(int i=0;i<SIZE;i++)
		//	printf("%d ",old[stateIndex].boardState[i]);
		//printf("%s\n","");
		if(old[stateIndex].g<UpperLimit) UpperLimit=old[stateIndex].g;
		printf("%s %d\n","found goal-->>",UpperLimit);
		//goalDepth=old[stateIndex].g;
		return 100;

	}
	newg=g+1;
	for (int newMove = 0; newMove < SIZE; newMove++)
	{
		if (!OperMat[PrevMove][newMove])
		 {
			 //printf("%s %d\n","not allowed move: ",opindex);
			continue;
		}

		//else - generate the potential child by modifying the child
		MakeMove(stateIndex,newMove);
		if(IsGoal(stateIndex))
		{
		//printf("%s\n","found goal");
		//for(int i=0;i<SIZE;i++)
		//	printf("%d ",old[stateIndex].boardState[i]);
		//printf("%s\n","");
			if(newg<UpperLimit) UpperLimit=newg;
		//printf("%s %d\n","found goal-->>",UpperLimit);
		//goalDepth=old[stateIndex].g;

		}

		hash=CalcHash(old[stateIndex].boardState);
		newindex=SearchHash(old[stateIndex].boardState,hash);
		if(newindex==stateIndex) newindex=-1;
		newcost=1000;
		//newg=g+1;
        //ConvertStateToDual(stateIndex);
		//newh=GetHuristicRegular(DualState);
		newh=GetHuristicRegular(stateIndex,0);
		newh=MAX(h-1,newh);

		if(newg+newh<=old[stateIndex].g+old[stateIndex].h) //need to add to CLOSE
		{
			int IEstate=-1;
			bool IEflag=false;
			if(newindex==-1)//If this is a new node - add to CLOSE
			{
				int cindex=FAdd2Close(stateIndex,hash,newMove,newg,newh,newg+newh);
				IEstate=cindex;
				IEflag=true;
				//perform the IIIExpand
			}
			else//the node is already in memory
			{
				if(old[newindex].heaplink==-1)//if the node is in CLOSE
				{
					//if(old[newindex].g>newg)
					if(old[newindex].cost>old[stateIndex].cost)
					{
						old[newindex].h=newh;
						old[newindex].g=newg;
						old[newindex].cost=lookahead;
						IEstate=newindex;
						IEflag=true;
						//perform the IIIExpand
					}
				}
				else //the node is in OPEN
				{
					if(old[newindex].cost>old[stateIndex].cost)
					{
						//Need to delete it from the OPEN
						DeleteFromOpenList(newindex);
						old[newindex].h=newh;
						old[newindex].g=newg;
						old[newindex].PrevMove=newMove;
						IEstate=newindex;
						IEflag=true;
					}//end if
					
				}//end else node in OPEN
			}//end else node in memory
		
			//Immediate Generate nodes based on flags
			if(IEflag==true)
			{
				//printf("%s\n","IE");
				//if(IEstate==173974) printf("%s\n","sending to IE");
				IE++;
				GExpandNode1(IEstate,newg,newh,newMove,lookahead);
			}

		}
		else
		{
		
		//if(newg<lookahead)
		//{
			//if(newg+newh==lookahead) printf("%s\n","something fishy");
			//printf("%s %d %s %d\n","performing LH, g=",newg,"h=",newh);
			//LHResult=FLimitedLookAhead1(stateIndex,newg,newh,lookahead,newMove);
			LHResult=GIDAStar(stateIndex,newg,newh,newg+lookahead,newMove);
			//printf("%s","after :");
			//for(int i=0;i<SIZE;i++)
			//	printf("%d ",old[stateIndex].boardState[i]);
			//printf("%s\n","");
			//printf("%s %d\n","*** *** End of lookahead, cost=",LHResult);
			//string mystr1;
			//getline (cin,mystr1);

			newcost=LHResult;
			//newh=LHResult-newg;
			
		////}
		//else
		//{
		//	newcost=newg+newh;
		////	//printf("%s %d\n","f bigger than lookaahead, no LH required",newcost);
		//}
			//printf("%s %d %s %d %s %d\n","--<< childh=",newh,"childg=",newg,"childcost=",newcost);
			//string mystr1;
			//getline (cin,mystr1);
		//if(newg+newh<=old[stateIndex].cost) newcost=old[stateIndex].cost;
		//else
		//	newcost=newg+newh;
		// if the child is unique - add it to the OPEN list
		
		if(newindex==-1)
		{
			if(newcost<UpperLimit)
			{
			//printf("%s %d %s %d %s %d %s %d\n","Adding - cost=",newcost," f=",newg+newh,"lookahead=",lookahead,"parentf=",g+h);
			FInsertHash(stateIndex,hash,newMove,newg,newh,newcost);	
			}
		}
		else
		{
			if(newg<old[newindex].g)
			{
				if(old[newindex].heaplink==-1)
				{
					if(newcost<UpperLimit)
					{
					old[newindex].g=-1;
					old[newindex].h=-1;
					old[newindex].cost=0;
					for (int i=0;i<SIZE;i++)
						old[newindex].boardState[i]=-1;
					//printf("%s %d %s %d %s %d %s %d\n","Reclose - cost=",newcost," f=",newg+newh,"lookahead=",lookahead,"parenth=",g+h);
					FInsertHash(stateIndex,hash,newMove,newg,newh,newcost);
					}
				}
				else
				{
					if(newcost<UpperLimit)
					{
					//	printf("%s\n","~~~~~~~~~~~~~~~~~~~ ReOpening ~~~~~~~~~~~~~~~~~");
						//string mystr1;
						//getline (cin,mystr1);

					if(old[newindex].h!=newh) old[newindex].h=newh;
					if(old[newindex].cost!=newcost) old[newindex].cost=newcost;
					FReOpen(newindex,newg,newMove);
					}
				}
			}
		}
		//}
		}
		MakeMove(stateIndex,newMove);
	}
	//string mystr1;
	//getline (cin,mystr1);
	return -1;
}


int oGExpandNode1(int stateIndex, int g, int h, int PrevMove,int lookahead)
{
	int hash;
	int newindex;
	int newh;
	int newg;
	int newcost;
	FILE *solution;
	int LHResult;


	LHResult=-1;
	newcost=1000;
	//printf("%s %d %s %d %s %d %s %d\n","parentg=",g,"parenth=",h,"lookahead=",lookahead,"cost=",old[stateIndex].cost);
	//string mystr1;
	//getline (cin,mystr1);
	if(IsGoal(stateIndex))
	{
		//printf("%s\n","found goal");
		//for(int i=0;i<SIZE;i++)
		//	printf("%d ",old[stateIndex].boardState[i]);
		//printf("%s\n","");
		if(old[stateIndex].g<UpperLimit) UpperLimit=old[stateIndex].g;
		printf("%s %d\n","found goal-->>",UpperLimit);
		//goalDepth=old[stateIndex].g;
		return 100;

	}
	for (int newMove = 0; newMove < SIZE; newMove++)
	{
		newcost=1000;
		if (!OperMat[PrevMove][newMove])
		 {
			 //printf("%s %d\n","not allowed move: ",opindex);
			continue;
		}

		//else - generate the potential child by modifying the child
		MakeMove(stateIndex,newMove);

		hash=CalcHash(old[stateIndex].boardState);
		newindex=SearchHash(old[stateIndex].boardState,hash);
		if(newindex==stateIndex) newindex=-1;

		newg=g+1;
        //ConvertStateToDual(stateIndex);
		//newh=GetHuristicRegular(DualState);
		newh=GetHuristicRegular(stateIndex,0);
		newh=MAX(h-1,newh);
		//printf("%s %d %s %d %s %d\n","-->> childh=",newh,"childg=",newg,"childcost=",newcost);
		
		if(newg<=lookahead)
		{
			LHResult=GLimitedLookAhead1(stateIndex,newg,newh,lookahead,newMove);
			//if(LHResult==10000)
			//{
			//	MakeMove(stateIndex,newMove);
			//	return 100;
			//}
			newcost=LHResult;
			//printf("%s %d %s %d %s %d\n","--<< childh=",newh,"childg=",newg,"childcost=",newcost);
			//string mystr1;
			//getline (cin,mystr1);
		}
		else
		{
			newcost=newg+newh;
		}
		//if(newg+newh<=old[stateIndex].cost) newcost=old[stateIndex].cost;
		//else
		//	newcost=newg+newh;
		// if the child is unique - add it to the OPEN list
		
		if(newindex==-1)
		{
			if(newcost<UpperLimit)
			{
			//printf("%s %d %s %d %s %d\n","Adding - cost=",newcost," f=",newg+newh,"lookahead=",lookahead);
		//	printf("%s %d %s %d %s %d\n","childh=",newh,"childg=",newg,"childcost=",newcost);
			FInsertHash(stateIndex,hash,newMove,newg,newh,newcost);	
			}
		}
		else
		{
			if(newg<old[newindex].g)
			{
				if(old[newindex].heaplink==-1)
				{
					if(newcost<UpperLimit)
					{
					old[newindex].g=-1;
					old[newindex].h=-1;
					old[newindex].cost=0;
					for (int i=0;i<SIZE;i++)
						old[newindex].boardState[i]=-1;
				//	printf("%s %d %s %d %s %d\n","reclose - childh=",newh,"childg=",newg,"childcost=",newcost);
					FInsertHash(stateIndex,hash,newMove,newg,newh,newcost);
					}
				}
				else
				{
					if(newcost<UpperLimit)
					{
					if(old[newindex].h!=newh) old[newindex].h=newh;
					if(old[newindex].cost!=newcost) old[newindex].cost=newcost;
				//	printf("%s %d %s %d %s %d\n","reopen - childh=",newh,"childg=",newg,"childcost=",newcost);
					FReOpen(newindex,newg,newMove);
					}
				}
			}
		}
		MakeMove(stateIndex,newMove);
	}
	//printf("%s\n","done");
	//string mystr;
	//getline (cin,mystr);

	return -1;
}


void ClassicAStar (short s[SIZE],char* algorithmName)
{
	//Variables
	int blank;
	int CurrentHashValue;
	int CurrentDepth;
	int CurrentOpenNode; //next node in the open list to check
	double startclock;
	double endclock;
	double innerclock;
	double time2loop;
	FILE *solution;


	//Init Hash table
	for (int i = 0; i< MAX; i++)                    /* empty hash table */
    {
		old[i].g = -1;                  /* only g value checked for emptiness */
		old[i].heaplink=-1;
		bucket[i] = MAX;
	}

	for (int t=0;t<FULL;t++)
	{
		heap[t]=-1;
	}


	//Init Open List pointers
	OpenStart=0; // beginning of the open list
	OpenEnd = 0; //End of the open list

	//Init next free loaction index in hash table
	empty=0;

	//Init counters
	maxopen=0;
	copen=0;
	expanded=0;                               
	generated=0;                             
	stored=0;
	reopened=0;
	reclose=0;
	opened=0;
	closed=0;
	CurrentOpenNode=0;
	ImmediateGenerated=0;
	IE=0;
	UpperLimit=1101; //TODO - need to find logical upper limit

	//Init goal test inidicator
	CurrentDepth=0;
	//duplicateFlag = 1;
	duplicatCounter=0;
	goalDepth=0;
	sameV=0;




	//Find the blank position
	for (blank=0;blank<SIZE;blank++)
		if (s[blank]==0) break;

	//Start counting time
	startclock = (double)clock();
	CurrentHashValue=CalcHash(s);
	//Insert the initial state to the hash table and update the open list
	for (int word = 0;word<SIZE;word++)
		old[empty].boardState[word]=s[word];
	old[empty].PrevMove = SIZE;
	old[empty].g = 0;
//	ConvertStateToDual(0);
	//old[empty].h=bestf=GetHuristicRegular(DualState);
	old[empty].h=bestf=GetHuristicRegular(0,0);
	old[empty].link = bucket[CurrentHashValue];      /* next pointer to old first element */
	old[empty].heaplink=0;
	 bucket[CurrentHashValue] = empty;               /* new state is at head of hash chain */
	 int f = old[empty].g + old[empty].h; 
	empty++;
	heap[0]=0;
	//
	if (DEBUG_PRINTS){
		printf("%s","first node h = ");
		printf("%d\n",old[empty-1].h);
		printf("%s %d\n","expand before=",expanded);
	}

	
	//Searching loop:
	//While the goal was not found and hash table is not full and the current f value is lower than the upper limit
	//while(!IsGoal(heap[0]) && stored <FULL && OpenStart>=0)
	while(CurrentDepth!=100 && stored <FULL && OpenStart>=0)
	{

		bestf=old[heap[0]].h+old[heap[0]].g;
		CurrentOpenNode=heap[0];
		DeleteFromOpenList(CurrentOpenNode); //delete the node expanded from the open list
			//printf("%s %d\n","bestf=",bestf);
		//CurrentDepth=ClassicExpandNode(CurrentOpenNode,old[CurrentOpenNode].g,old[CurrentOpenNode].h,old[CurrentOpenNode].PrevMove);
		CurrentDepth=CExpandNode1(CurrentOpenNode,old[CurrentOpenNode].g,old[CurrentOpenNode].h,old[CurrentOpenNode].PrevMove);
		//if(UpperLimit<1000) 
		//{
		//	printf("%d\n",CurrentDepth);
		//	string mystr;
		//	getline (cin,mystr);
		//}

		expanded++;
	}

	endclock = (double)clock();
	time2search = (endclock-startclock)/(double)CLOCKS_PER_SEC;

	if(IsGoal(heap[0])) goalDepth=old[heap[0]].g;

	goalDepth=UpperLimit;

	PrintResult(algorithmName);
	printf("%s","expanded= ");
	printf("%d \n",expanded);
	printf("%s","IE= ");
	printf("%d \n",IE);
	printf("%s","stored = ");
	printf("%d \n",stored);
		printf("%s","reopened = ");
	printf("%d \n",reopened);
		printf("%s","IG= ");
	printf("%d \n",ImmediateGenerated);
	printf("%s","opened = ");
		printf("%d \n",opened);
	printf("%s","closed = ");
	printf("%d \n",closed);
	printf("%s %d\n","maxopen = ",maxopen);
	printf("%s","goalDepth = ");
	printf("%d \n",goalDepth);
	printf("%s", "Start Time = ");
	printf ("%f \n",startclock);
	printf("%s", "Stop Time = ");
	printf ("%f \n",endclock);
	printf ("%s","sameV = ");
	printf ("%d \n",sameV);
	printf("%s", "time2search = ");
	printf ("%f \n",time2search);
	//string mystr;
	//getline (cin,mystr);


}




/**
Sets up variables for the search:
old - Sets g and heap link to -1
bucket - MAX
heap - with -1
**/
void setupSearch(){
	//Init Hash table
	for (int i = 0; i< MAX; i++)                    /* empty hash table */
    {
		old[i].g = -1;                  /* only g value checked for emptiness */
		old[i].heaplink=-1;
		bucket[i] = MAX;
	}

	for (int t=0;t<FULL;t++)
	{
		heap[t]=-1;
	}

	//Init Open List pointers
	OpenStart=0; // beginning of the open list
	OpenEnd = 0; //End of the open list

	//Init next free loaction index in hash table
	empty=0;

	//Init counters
	maxopen=0;
	copen=0;
	expanded=0;                               
	generated=0;                             
	stored=0;
	reopened=0;
	reclose=0;
	opened=0;
	closed=0;

	ImmediateGenerated=0;
	IE=0;
	UpperLimit=1101; //TODO - need to find logical upper limit

	//duplicateFlag = 1;
	duplicatCounter=0;
	goalDepth=0;
	sameV=0;
}

/**
Run an iteration of Classic IDA* 
**/
int IDAStarIteration(short state[SIZE],int g, int h, int bound,int PrevMove)
{
	int newg;
	int newh;
	int newf;
	bool breakTest=false;

	newg=g+1;
	for (int newMove=0;newMove<SIZE;newMove++)
	{
		if (!OperMat[PrevMove][newMove]) // Illegal move
			continue;

		MakeMove(state,newMove);
		ImmediateGenerated++;
		newh=GetHuristicRegular(state,0);
		newh=MAX(newh,h-1); // Pathmax Rule 1

		newf=newg+newh;
		if(IsGoal(state))//&& newf<=lookahead) 
		{
			if(newg<UpperLimit){ 
				UpperLimit=newg;
			}

			//QA - maybe I need to return 
			//[ANSWER: In a domain with non-uniform edge cost you need to continue]
		}
		else
		{
			// Continue DFS recursion if limit has not been reached yet
			if(newf<=bound && newf<UpperLimit )//&& lookahead<UpperLimit)
			{
				IDAStarIteration(state,newg,newh,bound,newMove);
				expanded++;
			}
			if((newf<nextIDAStarBound) && (newf>bound)){
				nextIDAStarBound = newf;
			}

		}
		MakeMove(state,newMove);
	}

	return nextIDAStarBound;
}

/**
Run an iteration of IDA* with BPMX
**/
int IDAStarIterationWithBPMX(short state[SIZE],int g, int h, int bound,int PrevMove)
{
	int newg;
	int newh;
	int newf;
	bool breakTest=false;
	int updatedParentH = h;
	newg=g+1;
	for (int newMove=0;newMove<SIZE;newMove++)
	{
		if (!OperMat[PrevMove][newMove]) // Illegal move
			continue;

		MakeMove(state,newMove);
		ImmediateGenerated++;
		newh=GetHuristicRegular(state,0);
		newh=MAX(newh,updatedParentH-1); // BPMX PARENT TO CHILD

		newf=newg+newh;
		if(IsGoal(state))//&& newf<=lookahead) 
		{
			if(newg<UpperLimit){ 
				UpperLimit=newg;
			}

			//QA - maybe I need to return 
			//[ANSWER: In a domain with non-uniform edge cost you need to continue]
		}
		else
		{
			// Continue DFS recursion if limit has not been reached yet
			if(newf<=bound && newf<UpperLimit )//&& lookahead<UpperLimit)
			{
				newh = IDAStarIteration(state,newg,newh,bound,newMove);				
				if(updatedParentH<newh-1) // BPMX CHILD TO PARENT
					updatedParentH=newh-1;
				expanded++;
			}
			if((newf<nextIDAStarBound) && (newf>bound)){
				nextIDAStarBound = newf;
				if (updatedParentH<newh-1){ // BPMX CHILD TO PARENT
					updatedParentH=newh-1;
				}
			}

		}
		MakeMove(state,newMove);
		if (updatedParentH>bound)
			break;
	}

	return updatedParentH;
}

/**
General IDA* 
**/
void GeneralIDAStar(char* name, short state[SIZE],int (*iterationFunction) (short[SIZE],int,int,int,int)){
	//Variables
	int blank;
	int CurrentHashValue;
	int CurrentDepth=0;
	int CurrentOpenNode=0; //next node in the open list to check
	double startclock;
	double endclock;
	double innerclock;
	double time2loop;
	FILE *solution;
	
	// Setup datastructures
	setupSearch();
	
	//Start counting time
	startclock = (double)clock();
	nextIDAStarBound = 1;
	int bound = nextIDAStarBound;
	int h = GetHuristicRegular(state,0);
	while(UpperLimit>=bound){
		nextIDAStarBound = INFINITY;
		iterationFunction(state,0,h,bound,SIZE); // Updates nextIDAStarBound
		bound = nextIDAStarBound;
		if (DEBUG_PRINTS) printf(" IDA* Threshold=%d, expanded so far=%d\n",bound,expanded);
	}
	endclock = (double)clock();

	time2search = (endclock-startclock)/(double)CLOCKS_PER_SEC;
	goalDepth=UpperLimit;

	PrintResult(name);
	printf("%s","expanded= ");
	printf("%d \n",expanded);
	printf("%s","IE= ");
	printf("%d \n",IE);
	printf("%s","stored = ");
	printf("%d \n",stored);
	printf("%s","reopened = ");
	printf("%d \n",reopened);
	printf("%s","IG= ");
	printf("%d \n",ImmediateGenerated);
	printf("%s","opened = ");
	printf("%d \n",opened);
	printf("%s","closed = ");
	printf("%d \n",closed);
	printf("%s %d\n","maxopen = ",maxopen);
	printf("%s","goalDepth = ");
	printf("%d \n",goalDepth);
	printf("%s", "Start Time = ");
	printf ("%f \n",startclock);
	printf("%s", "Stop Time = ");
	printf ("%f \n",endclock);
	printf ("%s","sameV = ");
	printf ("%d \n",sameV);
	printf("%s", "time2search = ");
	printf ("%f \n",time2search);
}

/**
Classic IDA* (No BPMX)
**/
void ClassicIDAStar(short state[SIZE])
{
	//Variables
	int blank;
	int CurrentHashValue;
	int CurrentDepth=0;
	int CurrentOpenNode=0; //next node in the open list to check
	double startclock;
	double endclock;
	double innerclock;
	double time2loop;
	FILE *solution;
	
	// Setup datastructures
	setupSearch();
	
	//Start counting time
	startclock = (double)clock();
	nextIDAStarBound = 1;
	int bound = nextIDAStarBound;
	int h = GetHuristicRegular(state,0);
	while(UpperLimit>=bound){
		nextIDAStarBound = INFINITY;
		IDAStarIteration(state,0,h,bound,MAX); // Updates nextIDAStarBound
		bound = nextIDAStarBound;
		if (DEBUG_PRINTS) printf(" IDA* Threshold=%d, expanded so far=%d\n",bound,expanded);
	}
	endclock = (double)clock();

	time2search = (endclock-startclock)/(double)CLOCKS_PER_SEC;
	goalDepth=UpperLimit;

	PrintResult("IDA*");
	printf("%s","expanded= ");
	printf("%d \n",expanded);
	printf("%s","IE= ");
	printf("%d \n",IE);
	printf("%s","stored = ");
	printf("%d \n",stored);
	printf("%s","reopened = ");
	printf("%d \n",reopened);
	printf("%s","IG= ");
	printf("%d \n",ImmediateGenerated);
	printf("%s","opened = ");
	printf("%d \n",opened);
	printf("%s","closed = ");
	printf("%d \n",closed);
	printf("%s %d\n","maxopen = ",maxopen);
	printf("%s","goalDepth = ");
	printf("%d \n",goalDepth);
	printf("%s", "Start Time = ");
	printf ("%f \n",startclock);
	printf("%s", "Stop Time = ");
	printf ("%f \n",endclock);
	printf ("%s","sameV = ");
	printf ("%d \n",sameV);
	printf("%s", "time2search = ");
	printf ("%f \n",time2search);
}















int IIIExpandNode(int stateIndex,int g,int h,int lookahead, int PrevMove)
{
	int blank;
	int newblank;
	int newindex;
	int opindex;

	int newg;
	int newh;
	int newf;
	int tile;
	int flag=-1;

	int hashval;

	//if(IsGoal(stateIndex))
	//{
	//	if(g<UpperLimit) UpperLimit=g;
	//	printf("%s\n","goal found");
	//	return 100;
	//}

	for (int newMove = 0; newMove < SIZE; newMove++)
	{
		if (!OperMat[PrevMove][newMove])
			continue;

		MakeMove(stateIndex,newMove);
		
		newg=g+1;

        //ConvertStateToDual(stateIndex);
		newh=GetHuristicRegular(stateIndex,0);
		if( IsGoal(stateIndex))
		{
			if (DEBUG_PRINTS){
				printf("%s %d %s %d\n","goal found in;",newg,"stateIndex=",stateIndex);
				for(int i=0;i<SIZE;i++)
					printf("%d ",old[stateIndex].boardState[i]);
				printf("%s\n","");
			}
			if(newg<UpperLimit) UpperLimit=newg;
		}

		newh=MAX(h-1,newh);
		newf=newh+newg;

		if(newf<UpperLimit)
		{
			 	hashval=CalcHash(old[stateIndex].boardState);
				newindex=SearchHash(old[stateIndex].boardState,hashval);
				if(newindex==stateIndex) newindex=-1;

				if(newf<=NextBestF) //need to add to CLOSE
				//if(newf<=0)
				{
					
					int IEstate=-1;
					bool IEflag=false;
					if(newindex==-1)//If this is a new node - add to CLOSE
					{
						Add2Close(stateIndex,hashval,newMove,newg,newh);
						IEstate=stateIndex;
						IEflag=true;
						//perform the IIIExpand
					}
					else//the node is already in memory
					{
						if(old[newindex].heaplink==-1)//if the node is in CLOSE
						{
							if(old[newindex].g>newg)
							{
								old[newindex].h=newh;
								old[newindex].g=newg;
								//IEstate=newindex;
								IEstate=stateIndex;
								IEflag=true;
								//perform the IIIExpand
							}
						}
						else //the node is in OPEN
						{
							if(old[newindex].g>newg)
							{
								//Need to delete it from the OPEN
								DeleteFromOpenList(newindex);
								//old[newindex].h=-1;
								//old[newindex].g=-1;
								//old[newindex].PrevMove=-1;
								//for (int i=0;i<SIZE;i++)
								//	old[newindex].boardState[i]=-1;
								old[newindex].h=newh;
								old[newindex].g=newg;
								old[newindex].PrevMove=newMove;
								IEstate=stateIndex;
								IEflag=true;
							}//end if
							
						}//end else node in OPEN
					}//end else node in memory
				
					//Immediate Generate nodes based on flags
					if(IEflag==true)
					{
						IE++;
						IIIExpandNode(IEstate,newg,newh,lookahead,newMove);
					}

				}//end if node cost is equal/lower than the current best node in OPEN
				else//need to add to OPEN
				{
					//printf("%s\n","Insert OPEN");
					if(newindex==-1) //if this is a new node - add to OPEN
					{
						InsertHash(stateIndex,hashval,newMove,newg,newh);
					}
					else //this node is already in memory
					{
							if(old[newindex].heaplink==-1)//if this node is in the CLOSE - need to delete from CLOSE and add to OPEN
							{
								//if(newindex==173974) printf("%s %d %s %d\n","found duplicate in:",stateIndex,"newindex=",newindex);
								//printf("%s %d %s %d\n","node in close",newindex,"node in open",stateIndex);
							//	//Need to delete it from CLOSE and add it to OPEN
								if(old[newindex].g>newg)
								{
									reclose++;
								old[newindex].g=-1;
								old[newindex].h=-1;
								old[newindex].PrevMove=-1;
								for(int i=0;i<SIZE;i++)
								{
									old[newindex].boardState[i]=-2;
								}
								InsertHash(stateIndex,hashval,newMove,newg,newh);
								}
								//InsertHash(newindex,hashval,newMove,newg,newh);
								//ReOpen(newindex,newg,newMove);

							}
							else //if this node is in the OPEN - need re-open
							{
								if(old[newindex].g>newg)//if we have a shorter path
								{
									reopened++;
								if(old[newindex].h!=newh) old[newindex].h=newh;
								ReOpen(newindex,newg,newMove);
								}
							}
					}
				}
		 }

		


		// printf("%s","Array before undo");
		//for (int i=0;i<SIZE;i++)
		//	printf("%d ",old[stateIndex].boardState[i]);
		//printf("%s\n","");
		MakeMove(stateIndex,newMove);
		//printf("%s","Array after undo move");
		//for (int i=0;i<SIZE;i++)
		//	printf("%d ",old[stateIndex].boardState[i]);
		//printf("%s\n","");
		//string mystr;
		//getline (cin,mystr);
		
	}//end for

return -1;
}
void IClassicAStar (short s[SIZE], int lookahead)
{
	//Variables
	int blank;
	int CurrentHashValue;
	int CurrentDepth;
	int CurrentOpenNode; //next node in the open list to check
	double startclock;
	double endclock;
	double innerclock;
	double time2loop;
	FILE *solution;


	//Init Hash table
	for (int i = 0; i< MAX; i++)                    /* empty hash table */
    {
		old[i].g = -1;                  /* only g value checked for emptiness */
		old[i].heaplink=-1;
		bucket[i] = MAX;
	}

	for (int t=0;t<FULL;t++)
	{
		heap[t]=-1;
	}


	//Init Open List pointers
	OpenStart=0; // beginning of the open list
	OpenEnd = 0; //End of the open list

	//Init next free loaction index in hash table
	empty=0;

	//Init counters
	maxopen=0;
	copen=0;
	expanded=0;                               
	generated=0;                             
	stored=0;
	reopened=0;
	reclose=0;
	opened=0;
	closed=0;
	CurrentOpenNode=0;
	ImmediateGenerated=0;
	IE=0;
	UpperLimit=1101; //TODO - need to find logical upper limit
	NextBestF=0;

	//Init goal test inidicator
	CurrentDepth=0;
	//duplicateFlag = 1;
	duplicatCounter=0;
	goalDepth=0;




	//Find the blank position
	for (blank=0;blank<SIZE;blank++)
		if (s[blank]==0) break;

	//Start counting time
	startclock = (double)clock();
	CurrentHashValue=CalcHash(s);
	//Insert the initial state to the hash table and update the open list
	for (int word = 0;word<SIZE;word++)
		old[empty].boardState[word]=s[word];
	old[empty].PrevMove = SIZE;
	old[empty].g = 0;
	//ConvertStateToDual(0);
	old[empty].h=bestf=GetHuristicRegular(0,0);
	old[empty].link = bucket[CurrentHashValue];      /* next pointer to old first element */
	old[empty].heaplink=0;
	 bucket[CurrentHashValue] = empty;               /* new state is at head of hash chain */
	 int f = old[empty].g + old[empty].h; 
	empty++;
	heap[0]=0;
	//
	if (DEBUG_PRINTS){
		printf("%s","first node h = ");
		printf("%d\n",old[empty-1].h);
		printf("%s %d\n","expand before=",expanded);
	}
	//Use IDA* with Lookahead as limit for the first node 

	
	 //if (lookahead>0) LimitedLookAhead(0,old[heap[0]].g,old[heap[0]].h,old[heap[0]].g+old[heap[0]].h+lookahead,old[heap[0]].PrevMove);
	
	//Searching loop:
	//While the goal was not found and hash table is not full and the current f value is lower than the upper limit
	//while((CurrentDepth!=100) && stored <FULL && old[heap[0]].h+old[heap[0]].g+lookahead<=UpperLimit && OpenStart>=0)//bestf+lookahead<UpperLimit)
	while((CurrentDepth!=100) && stored <FULL && old[heap[0]].h+old[heap[0]].g<UpperLimit && OpenStart>=0)//bestf+lookahead<UpperLimit)
	{

		//Search for the next best f in the OPEN list priotiy queue
		bestf=old[heap[0]].h+old[heap[0]].g;
		if(bestf<UpperLimit)

		innerclock=(double)clock();
		time2loop=(innerclock-startclock)/(double)CLOCKS_PER_SEC;

		if(time2loop>1800)
		{
			//printf("%s\n","somthing's fishy - need to check");
			printf("%s\n","Your 5 minutes time is up");
			printf("%s","bestf=");
			printf("%d\n",bestf);
			printf("%s","UpperLimit=");
			printf("%d\n",UpperLimit);
			break;
		}

		CurrentOpenNode=heap[0];
		//If the current node is a goal - stop the loop
		if (old[CurrentOpenNode].h==0 && old[CurrentOpenNode].g>UpperLimit)
		{
			printf("%s\n","Found goal!");
			CurrentDepth=100;
			goalDepth=old[CurrentOpenNode].g;
		}
		//Else (meaning, this is a node which is not a goal and with f value lower than upper limit - need to develop it
		else
		{


			DeleteFromOpenList(CurrentOpenNode); //delete the node expanded from the open list
			//if(heap[0]==0) 
			//{
			//	heap[0]=-1;
			//	NextBestF=0;
			//}
			//else
			NextBestF=old[CurrentOpenNode].g+old[CurrentOpenNode].h;

			//printf("%s %d %s %d %s %d\n","heap[0]=",heap[0],"eg=",old[CurrentOpenNode].g,"eh=",old[CurrentOpenNode].h);
			CurrentDepth=IIIExpandNode(CurrentOpenNode,old[CurrentOpenNode].g,old[CurrentOpenNode].h,0,old[CurrentOpenNode].PrevMove);

			expanded++;
			
		}
	}
	goalDepth=UpperLimit;
	endclock = (double)clock();
	time2search = (endclock-startclock)/(double)CLOCKS_PER_SEC;
	PrintResult("IA*");
	printf("%s","expanded= ");
	printf("%d \n",expanded);
	printf("%s","IE= ");
	printf("%d \n",IE);
	printf("%s","stored = ");
	printf("%d \n",stored);
		printf("%s","reopened = ");
	printf("%d \n",reopened);
		printf("%s","IG= ");
	printf("%d \n",ImmediateGenerated);
	printf("%s","opened = ");
		printf("%d \n",opened);
	printf("%s","closed = ");
	printf("%d \n",closed);
	printf("%s %d\n","maxopen = ",maxopen);
	printf("%s","goalDepth = ");
	printf("%d \n",goalDepth);
	printf("%s", "Start Time = ");
	printf ("%f \n",startclock);
	printf("%s", "Stop Time = ");
	printf ("%f \n",endclock);
	printf ("%s","Duplicated = ");
	printf ("%d \n",duplicatCounter);
	printf("%s", "time2search = ");
	printf ("%f \n",time2search);
	//string mystr;
	//getline (cin,mystr);

}

int LimitedLookAhead(int stateIndex,int g, int h,int lookahead, int PrevMove)
{
	int newg;
	int newh;
	int newf;
	FILE *solution;

	int result=0;
	if(IsGoal(stateIndex))
	{
		if(g<UpperLimit) UpperLimit=g;
		//printf("%s\n","---is a goal---");

		//string mystr;
		//getline (cin,mystr);
		return -1;
	}

	if(g+h>lookahead)
	{
		//printf("%s\n","lookahead exceeded");

		//string mystr;
		//getline (cin,mystr);
		return -2;
	}
	//solution=fopen("LH_1.txt","a");
	//fprintf(solution,"%s ","lh,");
	//	for (int j=0;j<SIZE;j++)
	//		fprintf(solution,"%d ",old[stateIndex].boardState[j]);
	//		fprintf(solution,",%d,%d,%d,\n",g,h,lookahead);
	//	fclose(solution);
	//if(g+h>lookahead) return 100;
	newg=g+1;

	for (int newMove = 0; newMove < SIZE; newMove++)
	{
		if (!OperMat[PrevMove][newMove])
		 {
			 //printf("%s %d\n","not allowed move: ",opindex);
			continue;
		}

		//else - generate the potential child by modifying the child
		MakeMove(stateIndex,newMove);
        //ConvertStateToDual(stateIndex);
		newh=GetHuristicRegular(stateIndex,0);
		//if(h-newh>1) printf("%s %d %s %d\n","h=",h,"newh=",newh);
		newh=MAX(h-1,newh);
		ImmediateGenerated++;
		newf=newh+newg;
		//printf("%s %d %s %d %s %d %s %d %s %d %s %d\n","childg=", newg,"childh=",newh,"parenth=",h,"parentf=",h+g, "childf=",newg+newh,"lookahead=",lookahead);
		if(IsGoal(stateIndex))
		{
			if(newg<UpperLimit) UpperLimit=newg;
			//printf("%s %d %s %d %s %d\n","goal found in depth - ",newg," stateIndex=",stateIndex," move=",newMove);
			//MakeMove(stateIndex,newMove);
			//return -2;
			//printf("%s %d %s %d %s %d\n","stateIndex=",stateIndex," IPF=",h+g," OrPF=",old[stateIndex].g+old[stateIndex].h);
			//string mystr;
			//getline (cin,mystr);

		}

		
		//solution=fopen("LH_1.txt","a");
		//fprintf(solution,"%s ","lhc,");
		//for (int j=0;j<SIZE;j++)
		//	fprintf(solution,"%d ",old[stateIndex].boardState[j]);
		//	fprintf(solution,",%d,%d,%d,\n",newg,newh,lookahead);
		//fclose(solution);
		
		//if(newg+newh>lookahead)
		//{
		//	MakeMove(stateIndex,newMove);
		//	return -1;
		//}
		//else
		//{
		//if(newf<=lookahead)
		//{
			//printf("%s %d %s %d %s %d\n","f=",h+g,"newf=",newf,"lookahead=",lookahead);
			if(newf<UpperLimit)
			{
				result=LimitedLookAhead(stateIndex,newg,newh,lookahead,newMove);
			}
		//}
		//}

		//if (result==-1)
		//{
		//	MakeMove(stateIndex,newMove);
		//	return result;
		//}
		//}
		MakeMove(stateIndex,newMove);
		//if(result==100) return 100;

	}
	if (result==-2) return -2;
	else return 0;
}


int ILHExpandNode(int stateIndex,int g,int h,int lookahead, int PrevMove)
{
	int blank;
	int newblank;
	int newindex;
	int opindex;

	int newg;
	int newh;
	int newf;
	int tile;
	int flag=-1;

	int hashval;

	//if(IsGoal(stateIndex))
	//{
	//	if(g<UpperLimit) UpperLimit=g;
	//	printf("%s\n","goal found");
	//	return 100;
	//}

	


	for (int newMove = 0; newMove < SIZE; newMove++)
	{
		if (!OperMat[PrevMove][newMove])
		 {
			 //printf("%s %d\n","not allowed move: ",opindex);
			continue;
		}

		//else - generate the potential child by modifying the child
		//printf("%s","Array before move");
		//for (int i=0;i<SIZE;i++)
		//	printf("%d ",old[stateIndex].boardState[i]);
		//printf("%s\n","");
		MakeMove(stateIndex,newMove);
		//printf("%s","Array after move");
		//for (int i=0;i<SIZE;i++)
		//	printf("%d ",old[stateIndex].boardState[i]);
		//printf("%s\n","");
		

		//hashval=CalcHash(old[stateIndex].boardState);
		//newindex=SearchHash(old[stateIndex].boardState,hashval);
		//if(newindex==stateIndex) newindex=-1;

		newg=g+1;

        //ConvertStateToDual(stateIndex);
		newh=GetHuristicRegular(stateIndex,0);
		if(newh==0 && IsGoal(stateIndex))
		{
			printf("%s %d\n","goal found in;",newg);
			if(newg<UpperLimit) UpperLimit=newg;
		}

		newh=MAX(h-1,newh);

		 newf=newh+newg;
		// printf("%s %d %s %d\n","newf=",newf,"NextBestF=",NextBestF);
		// string mystr;
		//getline (cin,mystr);


		 if(newf<UpperLimit)
		 {
			 	hashval=CalcHash(old[stateIndex].boardState);
				newindex=SearchHash(old[stateIndex].boardState,hashval);
				if(newindex==stateIndex) newindex=-1;

				if(newf<=NextBestF) //need to add to CLOSE
				//if(newf<=0)
				{
					int IEstate=-1;
					bool IEflag=false;
					if(newindex==-1)//If this is a new node - add to CLOSE
					{
						Add2Close(stateIndex,hashval,newMove,newg,newh);
						IEstate=stateIndex;
						IEflag=true;
						//perform the IIIExpand
					}
					else//the node is already in memory
					{
						if(old[newindex].heaplink==-1)//if the node is in CLOSE
						{
							if(old[newindex].g>newg)
							{
								old[newindex].h=newh;
								old[newindex].g=newg;
								IEstate=newindex;
								IEflag=true;
								//perform the IIIExpand
							}
						}
						else //the node is in OPEN
						{
							if(old[newindex].g>newg)
							{
								//Need to delete it from the OPEN
								DeleteFromOpenList(newindex);
								old[newindex].h=newh;
								old[newindex].g=newg;
								old[newindex].PrevMove=newMove;
								IEstate=newindex;
								IEflag=true;
							}//end if
							
						}//end else node in OPEN
					}//end else node in memory
				
					//Immediate Generate nodes based on flags
					if(IEflag==true)
					{
						//printf("%s\n","IE");
						IE++;
						if(newg+newh<=lookahead && newg+newh<UpperLimit)
						LimitedLookAhead(stateIndex,newg,newh,lookahead,PrevMove);
						ILHExpandNode(IEstate,newg,newh,lookahead,newMove);
					}

				}//end if node cost is equal/lower than the current best node in OPEN
				else//need to add to OPEN
				{
					if(newg+newh<UpperLimit)
					{
					if(newindex==-1) //if this is a new node - add to OPEN
					{
						InsertHash(stateIndex,hashval,newMove,newg,newh);
					}
					else //this node is already in memory
					{
							if(old[newindex].heaplink==-1)//if this node is in the CLOSE - need to delete from CLOSE and add to OPEN
							{
								//printf("%s\n","node in close");
							//	//Need to delete it from CLOSE and add it to OPEN
								old[newindex].g=-1;
								old[newindex].h=-1;
								old[newindex].PrevMove=-1;
								for(int i=0;i<SIZE;i++)
								{
									old[newindex].boardState[i]=-1;
								}
								InsertHash(stateIndex,hashval,newMove,newg,newh);

							}
							else //if this node is in the OPEN - need re-open
							{
								if(old[newindex].g>newg)//if we have a shorter path
								{
								if(old[newindex].h!=newh) old[newindex].h=newh;
								ReOpen(newindex,newg,newMove);
								}
							}
					}
				}
				}
		 }
		MakeMove(stateIndex,newMove);		
	}//end for

return -1;
}
int LHExpandNode(int stateIndex,int g,int h,int lookahead, int PrevMove)
{
	int blank;
	int newblank;
	int newindex;
	int opindex;

	int newg;
	int newh;
	int newf;
	int tile;
	int flag=-1;

	int hashval;
	FILE *solution;
	int stateDual[SIZE];

	//if(IsGoal(stateIndex))
	//{
	//	if(g<UpperLimit) UpperLimit=g;
	//	//return 100;
	//}

	//int r=LimitedLookAhead(stateIndex,g,h,lookahead,PrevMove);
	//printf("%s\n","------ end of limit lookahead -------");
	for (int newMove = 0; newMove < SIZE; newMove++)
	{
		if (!OperMat[PrevMove][newMove])
		 {
			 //printf("%s %d\n","not allowed move: ",opindex);
			continue;
		}

		//else - generate the potential child by modifying the child
		MakeMove(stateIndex,newMove);

		//hashval=CalcHash(old[stateIndex].boardState);
		//newindex=SearchHash(old[stateIndex].boardState,hashval);
		//if(newindex==stateIndex) newindex=-1;

		newg=g+1;
		if(IsGoal(stateIndex))
		{
			if(newg<UpperLimit) UpperLimit=newg;
		}
        //ConvertStateToDual(stateIndex);
		newh=GetHuristicRegular(stateIndex,0);	
		newh=MAX(h-1,newh);


		 newf=newh+newg;

		 if(newf<UpperLimit)
		 {
			 	hashval=CalcHash(old[stateIndex].boardState);
				newindex=SearchHash(old[stateIndex].boardState,hashval);
				if(newindex==stateIndex) newindex=-1;

				
				//if(newf<=old[stateIndex].h+old[stateIndex].g) //need to add to CLOSE
				if(newf<=NextBestF)
				{
					int IEstate=-1;
					bool IEflag=false;
					if(newindex==-1)//If this is a new node - add to CLOSE
					{
						Add2Close(stateIndex,hashval,newMove,newg,newh);
						IEstate=stateIndex;
						IEflag=true;
						//perform the IIIExpand
					}
					else//the node is already in memory
					{
						if(old[newindex].heaplink==-1)//if the node is in CLOSE
						{
							if(old[newindex].g>newg)
							{
								old[newindex].h=newh;
								old[newindex].g=newg;
								IEstate=newindex;
								IEflag=true;
								//perform the IIIExpand
							}
						}
						else //the node is in OPEN
						{
							if(old[newindex].g>newg)
							{
								//Need to delete it from the OPEN
								DeleteFromOpenList(newindex);
								old[newindex].h=newh;
								old[newindex].g=newg;
								old[newindex].PrevMove=newMove;
								IEstate=newindex;
								IEflag=true;
							}//end if
							
						}//end else node in OPEN
					}//end else node in memory
				
					//Immediate Generate nodes based on flags
					if(IEflag==true)
					{
						LHExpandNode(IEstate,newg,newh,lookahead,newMove);
					}

				}//end if node cost is equal/lower than the current best node in OPEN
				else//need to add to OPEN
				{
					if(newindex==-1) //if this is a new node - add to OPEN
					{
						InsertHash(stateIndex,hashval,newMove,newg,newh);
					}
					else //this node is already in memory
					{
						if(old[newindex].g>newg)//if we have a shorter path
						{
							if(old[newindex].heaplink==-1)//if this node is in the CLOSE - need to delete from CLOSE and add to OPEN
							{
								//Need to delete it from CLOSE and add it to OPEN
								old[newindex].g=-1;
								old[newindex].h=-1;
								old[newindex].PrevMove=-1;
								for(int i=0;i<SIZE;i++)
								{
									old[newindex].boardState[i]=-1;
								}	
								InsertHash(stateIndex,hashval,newMove,newg,newh);
							}
							else //if this node is in the OPEN - need re-open
							{
								if(old[newindex].h!=newh) old[newindex].h=newh;
								ReOpen(newindex,newg,newMove);
							}
						}
					}
				}

			}


		MakeMove(stateIndex,newMove);
	}//end for

return -1;
}



void LHAStar2 (short s[SIZE], int lookahead)
{
	//Variables
	int blank;
	int CurrentHashValue;
	int CurrentDepth;
	int CurrentOpenNode; //next node in the open list to check
	double startclock;
	double endclock;
	double innerclock;
	double time2loop;
	FILE *solution;


	//Init Hash table
	for (int i = 0; i< MAX; i++)                    /* empty hash table */
    {
		old[i].g = -1;                  /* only g value checked for emptiness */
		old[i].heaplink=-1;
		old[i].h=-1;
		old[i].cost=INFINITY;
		for(int k=0;k<SIZE;k++)
			old[i].boardState[k]=-1;
		bucket[i] = MAX;
	}

	for (int t=0;t<FULL;t++)
	{
		heap[t]=-1;
	}

	for(int i=0;i<30;i++)
		CostArr[i]=-1;

	for(int i=0;i<30;i++)
		printf("%d ",CostArr[i]);
	printf("%s\n","");

	//Init Open List pointers
	OpenStart=0; // beginning of the open list
	OpenEnd = 0; //End of the open list

	//Init next free loaction index in hash table
	empty=0;
	sameV=0;

	//Init counters
	maxopen=0;
	copen=0;
	expanded=0;                               
	generated=0;                             
	stored=0;
	reopened=0;
	reclose=0;
	opened=0;
	closed=0;
	CurrentOpenNode=0;
	ImmediateGenerated=0;
	IE=0;
	UpperLimit=1101; //TODO - need to find logical upper limit

	//Init goal test inidicator
	CurrentDepth=0;
	//duplicateFlag = 1;
	duplicatCounter=0;
	goalDepth=0;
	NextBestF=0;
	LHFrom=0;




	//Find the blank position
	for (blank=0;blank<SIZE;blank++)
		if (s[blank]==0) break;

	//Start counting time
	startclock = (double)clock();
	CurrentHashValue=CalcHash(s);
	//Insert the initial state to the hash table and update the open list
	for (int word = 0;word<SIZE;word++)
		old[empty].boardState[word]=s[word];
	old[empty].PrevMove = SIZE;
	old[empty].g = 0;
	//ConvertStateToDual(0);
	old[empty].h=bestf=GetHuristicRegular(0,0);
	old[empty].link = bucket[CurrentHashValue];      /* next pointer to old first element */
	old[empty].heaplink=0;
	 bucket[CurrentHashValue] = empty;               /* new state is at head of hash chain */
	 int f = old[empty].g + old[empty].h; 
	 minf=10000;
	 //FIDAStar(0,0,bestf,bestf+lookahead,SIZE);
	 //old[empty].cost=minf;
	 old[empty].cost=f;
	empty++;
	heap[0]=0;
	//

	printf("%s","first node h = ");
	printf("%d\n",old[empty-1].h);
	printf("%s %d\n","expand before=",expanded);


	NextBestC=INFINITY;
	bestc=0;

	//Searching loop:
	//While the goal was not found and hash table is not full and the current f value is lower than the upper limit
	//while((CurrentDepth!=100) && stored <FULL && old[heap[0]].h+old[heap[0]].g+lookahead<=UpperLimit && OpenStart>=0)//bestf+lookahead<UpperLimit)
	while((CurrentDepth!=100) && stored <FULL && old[heap[0]].cost<UpperLimit && OpenStart>=0)//bestf+lookahead<UpperLimit)
	{
		//Search for the next best f in the OPEN list priotiy queue
		bestf=old[heap[0]].h+old[heap[0]].g;
		bestc=old[heap[0]].cost;
		NextBestC=bestc+1;
		while(OpenStart>1 && CostArr[NextBestC]==-1)
			NextBestC++;

		innerclock=(double)clock();
		CurrentOpenNode=heap[0];
        NextBestF=old[heap[0]].h+old[heap[0]].g;	
		FDeleteFromOpenList(CurrentOpenNode); //delete the node expanded from the open list
		CurrentDepth=FExpandNode1(CurrentOpenNode,old[CurrentOpenNode].g,old[CurrentOpenNode].h,old[CurrentOpenNode].PrevMove,old[CurrentOpenNode].g+old[CurrentOpenNode].h+lookahead);
		//FIDAStar(heap[0],old[heap[0]].g,old[heap[0]].h,old[heap[0]].h+old[heap[0]].g+lookahead,old[heap[0]].PrevMove);
		expanded++;	
	}
	printf("%s %d %s %d %s %d %s %d\n","h=",old[heap[0]].h," g=",old[heap[0]].g," cost=",old[heap[0]].cost,"lookahead=",lookahead);
	goalDepth=UpperLimit;
	endclock = (double)clock();
	time2search = (endclock-startclock)/(double)CLOCKS_PER_SEC;
	PrintResult("LHA*(%d)",lookahead);
	printf("%s","expanded= ");
	printf("%d \n",expanded);
	printf("%s","IE= ");
	printf("%d \n",IE);
	printf("%s","stored = ");
	printf("%d \n",stored);
		printf("%s","reopened = ");
	printf("%d \n",reopened);
		printf("%s","IG= ");
	printf("%d \n",ImmediateGenerated);
	printf("%s","opened = ");
		printf("%d \n",opened);
	printf("%s","closed = ");
	printf("%d \n",closed);
	printf("%s %d\n","maxopen = ",maxopen);
	printf("%s","goalDepth = ");
	printf("%d \n",goalDepth);
	printf("%s","sameV = ");
	printf("%d \n",sameV);
	printf("%s", "Start Time = ");
	printf ("%f \n",startclock);
	printf("%s", "Stop Time = ");
	printf ("%f \n",endclock);
	printf ("%s","Duplicated = ");
	printf ("%d \n",duplicatCounter);
	printf("%s %d %s %d\n","LHFrom=",LHFrom,"falseLH=",falseLH);
	printf("%s", "time2search = ");
	printf ("%f \n",time2search);
	//string mystr;
	//getline (cin,mystr);

}



int ClassicLHExpandNode(int stateIndex, int g, int h, int PrevMove,int lookahead)
{
	int hash;
	int newindex;
	int newh;
	int newg;
	FILE *solution;

	if(IsGoal(stateIndex))
	{
		printf("%s\n","found goal");
		for(int i=0;i<SIZE;i++)
			printf("%d ",old[stateIndex].boardState[i]);
		printf("%s\n","");
		goalDepth=old[stateIndex].g;
		return 100;

	}
	//printf("%s %d %s %d\n","f=",g+h," lookahead=",lookahead);
	LimitedLookAhead(stateIndex,g,h,lookahead,PrevMove);
	int stateDual[SIZE];
	//ConvertStateToDual(stateIndex,stateDual);
	//LimitedLookAhead(stateDual,g,h,lookahead,PrevMove);
	//string mystr;
	//getline (cin,mystr);
	for (int newMove = 0; newMove < SIZE; newMove++)
	{
		if (!OperMat[PrevMove][newMove])
		 {
			 //printf("%s %d\n","not allowed move: ",opindex);
			continue;
		}

		//else - generate the potential child by modifying the child
		MakeMove(stateIndex,newMove);
		newg=g+1;
        //ConvertStateToDual(stateIndex);
		//newh=GetHuristicRegular(DualState);
		newh=GetHuristicRegular(stateIndex,0);
		//if(h-newh>1)
		//{
		//	//printf("%s %d %s %d %s %d %s %d\n","h=",h,"g=",g,"newh=",newh,"newg=",newg);
		//	//string mystr;
		//	//getline (cin,mystr);

		//}
		//newh=MAX(h-1,newh);
		// if the child is unique - add it to the OPEN list
		if(newh+newg<UpperLimit)
		{
			hash=CalcHash(old[stateIndex].boardState);
			newindex=SearchHash(old[stateIndex].boardState,hash);
			if(newindex==stateIndex) newindex=-1;
			if(newindex==-1)
			{
				InsertHash(stateIndex,hash,newMove,newg,newh);	
			}
			else
			{
				if(newg<old[newindex].g)
				{
					//if(old[newindex].h!=newh)old[newindex].h=newh; 
					ReOpen(newindex,newg,newMove);				
				}
			}
		}
		MakeMove(stateIndex,newMove);
	}

	return -1;
}

void InsertHash2(short state[SIZE],int hashval,int PrevMove, int g, int h)
{
	//int word;                                            /* word in packed state */
	 int f;                                            /* combined merit function - no need - BFS*/
	 int index;                           /* index in hash table where state goes */
	 double copy_startclock;
     double copy_endclock;
	 double insert_startclock;
	 double insert_endclock;

	 index = empty++;           /* store in first empty location , empty defined globaly */
	 stored++;                        /* increment number of states in hash table */
	 opened++;
	 copen++;
	 if(maxopen<copen) maxopen=copen;

	for (int i=0;i<SIZE;i++)
	{
		old[index].boardState[i]=state[i];
	}
	old[index].PrevMove=PrevMove;
	

	//3. update h & g
	old[index].g=g;
	old[index].h=h;
	 
	

	 //TODO - need to re-think the assigment of the hash list per hashvalue (instead of adding the last node first, add it to the end of the list)
	 old[index].link = bucket[hashval];      /* next pointer to old first element */
	 bucket[hashval] = index;               /* new state is at head of hash chain */
	 f = old[index].g + old[index].h;


		//Heap OPEN list
		
	OpenStart++;

	heap[OpenStart]=index;
	old[index].heaplink=OpenStart;
	Heapify_up(OpenStart);

    if (f < bestf) bestf = f;

}

//int oBExpandNode(int stateIndex,int g,int h, int PrevMove)
//{
//	 struct child
//	 {                           
//		 short boardState[SIZE];
//		 short g;                                      /* distance from initial state */
//		 short h;                        /* static heuristic distance from goal state */
//		 short PrevMove;                                /* previous position of blank */
//		 bool add2Open;
//	 } children[SIZE];
//
//	int blank;
//	int newblank;
//	int newindex;
//	int opindex;
//
//	int newg;
//	int newh;
//	int newf;
//	int tile;
//	int flag=-1;
//
//	int hashval;
//	int maxH;  //holds the maximum H between all immediate children
//	int ChildNum;
//
//	FILE *solution;
//
//	//maxH=0;
//	maxH=h-1;
//	ChildNum=0;
//
//	// First check if the state is the goal
//	//printf("%s","checking for goal:");
//	//for (int i=0;i<SIZE;i++)
//	//	printf("%d ",old[stateIndex].boardState[i]);
//	//printf("%s\n","");
//	if(IsGoal(stateIndex))
//	{
//				printf("%s\n","found goal");
//		for(int i=0;i<SIZE;i++)
//			printf("%d ",old[stateIndex].boardState[i]);
//		printf("%s\n","");
//		goalDepth=old[stateIndex].g;
//		return 100;
//	}
//
//	//printf("%s\n","generating children");
//	// Generate all the immediate children:
//	newg=g+1;
//	for (int newMove = 0; newMove < SIZE; newMove++)
//	{
//		if (!OperMat[PrevMove][newMove])
//		 {
//			 //printf("%s %d\n","not allowed move: ",opindex);
//			continue;
//		}
//
//		//newblank=opindex;
//		MakeMove(stateIndex,newMove);
//		//printf("%s","the child node is:");
//		//for (int l=0;l<SIZE;l++)
//		//	printf("%d ",old[stateIndex].boardState[l]);
//
//		newh=GetHuristicRegular(stateIndex,0);
//		//printf("%s %d\n","child h=",newh);
//		maxH=MAX(maxH,newh-2);
//
//		 
//
//		 newf=newh+newg;
//		 //Add the child to the children list
//		 for(int i=0;i<SIZE;i++)
//			children[ChildNum].boardState[i]=old[stateIndex].boardState[i];
//		 children[ChildNum].add2Open=false;
//		 children[ChildNum].g=newg;
//		 children[ChildNum].h=newh;
//		 children[ChildNum].PrevMove=newMove;
//		 generated++;
//		 ChildNum++;
//		 MakeMove(stateIndex,newMove);
//		// printf("%s","state after undo:");
//		//for (int l=0;l<SIZE;l++)
//		//	printf("%d ",old[stateIndex].boardState[l]);
//		//printf("%s\n","");
//	}
//	//string mystr;
//	//getline (cin,mystr);
//
//
//	//printf("%s %d\n","maxh=",maxH);
//	//Now, update the children heuristic based on maxH found:
//	for (int i=0;i<ChildNum;i++)
//	{
//		//printf("%s %d\n","child h before change:",children[i].h);
//		children[i].h=MAX(maxH,children[i].h);
//		///printf("%s %d\n","child h after change1:",children[i].h);
//		//if(children[i].g+children[i].h<old[stateIndex].g+old[stateIndex].h)
//		//	children[i].h=old[stateIndex].h-1;
//		//printf("%s %d\n","child h after change2:",children[i].h);
//
//		//Search for the child in memory
//		hashval=CalcHash(children[i].boardState);
//		newindex=SearchHash(children[i].boardState,hashval);
//		if(newindex==stateIndex) newindex=-1;
//		//if(newindex!=-1 && old[newindex].PrevMove!=children[i].PrevMove)
//		//{
//		//	printf("%s\n","different prev moves");
//		//string mystr;
//		//getline (cin,mystr);
//		//}
//		//printf("%s %d\n","newindex=",newindex);
//
//		bool boo=true;
//		// if the state already exists
//		if(newindex!=-1)
//		{
//			
//			//Check if exists in close list
//			if(old[newindex].heaplink==-1)
//			{
//				//printf("%s","Found the state in close ");
//				//for(int j=0;j<SIZE;j++)
//				//	printf("%d ",old[newindex].boardState[j]);
//				//printf("%s %d %s %d\n","h=",old[newindex].h," g=",old[newindex].g);
//				//printf("%s %d %s %d\n","childh=",children[i].h," chilg=",children[i].g);
//				//string mystr;
//				//getline (cin,mystr);
//				FoundInC++;
//				//if(old[newindex].h>children[i].h)
//				//{
//				//	children[i].h=old[newindex].h;
//				//	UpdateH=true;
//				//}
//				if(old[newindex].g<=children[i].g)
//				{
//					boo=false;
//					//if(old[newindex].h>=children[i].h)
//					//boo=false;
//
//				}
//				//else
//				//if(old[newindex].g==children[i].g && old[newindex].h>=children[i].h)
//				//		boo=false;
//				//if(boo) //(g in close is lower than g in children)
//				else
//				{
//						boo=true;
//						for (int j=0;j<SIZE;j++)
//						old[newindex].boardState[j]=-1;
//					old[newindex].h=-1;
//					old[newindex].g=-1;
//				}
//				
//			}// end if - if in close list
//		
//			//else //the node is in the open list
//			if(old[newindex].heaplink!=-1)
//			{
//				//printf("%s","Found the state in close ");
//				//for(int j=0;j<SIZE;j++)
//				//	printf("%d ",old[newindex].boardState[j]);
//				//printf("%s %d %s %d\n","h=",old[newindex].h," g=",old[newindex].g);
//				//printf("%s %d %s %d\n","childh=",children[i].h," chilg=",children[i].g);
//				//string mystr;
//				//getline (cin,mystr);
//				boo=false;
//				FoundInO++;
//
//				//if(old[newindex].h>children[i].h)
//				//	children[i].h=old[newindex].h;
//				if(old[newindex].g>children[i].g)
//				{
//					//old[newindex].g=children[i].g;
//					boo=false;
//					if(old[newindex].h<children[i].h)
//						old[newindex].h=children[i].h;
//					ReOpen(newindex,children[i].g,children[i].PrevMove);
//				}
//
//				//---*********** this part worked ********************---
//				//if(old[newindex].g>children[i].g)
//				//{
//				//	old[newindex].g=children[i].g;
//				//	boo=false;
//				//	if(old[newindex].h<children[i].h)
//				//		old[newindex].h=children[i].h;
//				//	ReOpen(newindex,old[newindex].g,children[i].PrevMove);
//				//}
//				//else //(g in close is lower than g in children)
//				//{
//				//	if(old[newindex].g==children[i].g)
//				//	{
//				//	if(old[newindex].h<children[i].h)
//				//	{
//				//		boo=false;
//				//		old[newindex].h=children[i].h;
//				//		ReOpen(newindex,old[newindex].g,children[i].PrevMove);
//				//	}
//				//	}
//				//}//---*********** this part worked ********************---
//			}
//}//end if (for existing child)
//		else
//			boo=true;
//		//boo=true; //for testing
//		if (boo) 
//		{
//			//printf("%s\n","adding the child");
//			children[i].add2Open=true;
//		}
//		else
//		{
//			//printf("%s\n","NOT adding the child");
//			children[i].add2Open=false;
//		}
//
//		
//	//string mystr;
//	//getline (cin,mystr);
//	}//end for
//
//	//After updating the children heuristic, need to find new maxH
//	//maxH=0;
//	//for (int i=0;i<ChildNum;i++)
//	//{
//	//	maxH=MAX(maxH,children[i].h-2);
//	//}//end for
//
//	//printf("%s\n","-- before insert to open --");
//	// Now we can add the children to the OPEN list
//	for (int i=0;i<ChildNum;i++)
//	{
//		if(children[i].add2Open)
//		{
//			//printf("%s %d\n","childh before change:",children[i].h);
//			//children[i].h=MAX(maxH,children[i].h);
//			//printf("%s %d\n","childh after change:",children[i].h);
//			hashval=CalcHash(children[i].boardState);
//			InsertHash2(children[i].boardState,hashval,children[i].PrevMove,children[i].g,children[i].h);
//
//		}
//	}//end for
//	old[stateIndex].h=MAX(old[stateIndex].h,maxH-1);
//
//return -1;
//
//}

int BExpandNode(int stateIndex,int g,int h, int PrevMove)
{
	 struct child
	 {                           
		 short boardState[SIZE];
		 short g;                                      /* distance from initial state */
		 short h;                        /* static heuristic distance from goal state */
		 short PrevMove;                                /* previous position of blank */
		 bool add2Open;
	 } children[SIZE];

	int blank;
	int newblank;
	int newindex;
	int opindex;

	int newg;
	int newh;
	int newf;
	int tile;
	int flag=-1;

	int hashval;
	int maxH;  //holds the maximum H between all immediate children
	int ChildNum;

	FILE *solution;

	//maxH=0;
	maxH=h-1;
	ChildNum=0;

	// First check if the state is the goal
	//printf("%s","checking for goal:");
	//for (int i=0;i<SIZE;i++)
	//	printf("%d ",old[stateIndex].boardState[i]);
	//printf("%s\n","");
	if(IsGoal(stateIndex))
	{
				printf("%s\n","found goal");
		for(int i=0;i<SIZE;i++)
			printf("%d ",old[stateIndex].boardState[i]);
		printf("%s\n","");
		goalDepth=old[stateIndex].g;
		return 100;
	}

	//printf("%s\n","generating children");
	// Generate all the immediate children:
	newg=g+1;
	for (int newMove = 0; newMove < SIZE; newMove++)
	{
		if (!OperMat[PrevMove][newMove])
		 {
			 //printf("%s %d\n","not allowed move: ",opindex);
			continue;
		}

		//newblank=opindex;
		MakeMove(stateIndex,newMove);
		//printf("%s","the child node is:");
		//for (int l=0;l<SIZE;l++)
		//	printf("%d ",old[stateIndex].boardState[l]);
		//ConvertStateToDual(stateIndex);
		newh=GetHuristicRegular(stateIndex,0);
		//printf("%s %d\n","child h=",newh);
		maxH=MAX(maxH,newh-2);

		 

		 newf=newh+newg;
		 //Add the child to the children list
		 for(int i=0;i<SIZE;i++)
			children[ChildNum].boardState[i]=old[stateIndex].boardState[i];
		 children[ChildNum].add2Open=false;
		 children[ChildNum].g=newg;
		 children[ChildNum].h=newh;
		 children[ChildNum].PrevMove=newMove;
		 generated++;
		 ChildNum++;
		 MakeMove(stateIndex,newMove);
		// printf("%s","state after undo:");
		//for (int l=0;l<SIZE;l++)
		//	printf("%d ",old[stateIndex].boardState[l]);
		//printf("%s\n","");
	}
	//string mystr;
	//getline (cin,mystr);


	//printf("%s %d\n","maxh=",maxH);
	//Now, update the children heuristic based on maxH found:
	for (int i=0;i<ChildNum;i++)
	{
		//printf("%s %d\n","child h before change:",children[i].h);
		if(maxH>children[i].h) sameV++;
		children[i].h=MAX(maxH,children[i].h);
		///printf("%s %d\n","child h after change1:",children[i].h);
		//if(children[i].g+children[i].h<old[stateIndex].g+old[stateIndex].h)
		//	children[i].h=old[stateIndex].h-1;
		//printf("%s %d\n","child h after change2:",children[i].h);

		//Search for the child in memory
		hashval=CalcHash(children[i].boardState);
		newindex=SearchHash(children[i].boardState,hashval);
		if(newindex==stateIndex) newindex=-1;
		//if(newindex!=-1 && old[newindex].PrevMove!=children[i].PrevMove)
		//{
		//	printf("%s\n","different prev moves");
		//string mystr;
		//getline (cin,mystr);
		//}
		//printf("%s %d\n","newindex=",newindex);

		bool boo=true;
		// if the state already exists
		if(newindex!=-1)
		{
			
			//Check if exists in close list
			if(old[newindex].heaplink==-1)
			{
				//printf("%s","Found the state in close ");
				//for(int j=0;j<SIZE;j++)
				//	printf("%d ",old[newindex].boardState[j]);
				//printf("%s %d %s %d\n","h=",old[newindex].h," g=",old[newindex].g);
				//printf("%s %d %s %d\n","childh=",children[i].h," chilg=",children[i].g);
				//string mystr;
				//getline (cin,mystr);
				FoundInC++;
				//if(old[newindex].h>children[i].h)
				//{
				//	children[i].h=old[newindex].h;
				//	UpdateH=true;
				//}
				if(old[newindex].g<=children[i].g)
				{
					boo=false;
					//if(old[newindex].h>=children[i].h)
					//boo=false;

				}
				//else
				//if(old[newindex].g==children[i].g && old[newindex].h>=children[i].h)
				//		boo=false;
				//if(boo) //(g in close is lower than g in children)
				else
				{
					reclose++;
						boo=true;
						for (int j=0;j<SIZE;j++)
						old[newindex].boardState[j]=-1;
					old[newindex].h=-1;
					old[newindex].g=-1;
				}
				
			}// end if - if in close list
		
			//else //the node is in the open list
			if(old[newindex].heaplink!=-1)
			{
				//printf("%s","Found the state in close ");
				//for(int j=0;j<SIZE;j++)
				//	printf("%d ",old[newindex].boardState[j]);
				//printf("%s %d %s %d\n","h=",old[newindex].h," g=",old[newindex].g);
				//printf("%s %d %s %d\n","childh=",children[i].h," chilg=",children[i].g);
				//string mystr;
				//getline (cin,mystr);
				boo=false;
				FoundInO++;

				//if(old[newindex].h>children[i].h)
				//	children[i].h=old[newindex].h;
				if(old[newindex].g>children[i].g)
				{
					//old[newindex].g=children[i].g;
					boo=false;
					if(old[newindex].h<children[i].h)
						old[newindex].h=children[i].h;
					reopened++;
					ReOpen(newindex,children[i].g,children[i].PrevMove);
				}

				//---*********** this part worked ********************---
				//if(old[newindex].g>children[i].g)
				//{
				//	old[newindex].g=children[i].g;
				//	boo=false;
				//	if(old[newindex].h<children[i].h)
				//		old[newindex].h=children[i].h;
				//	ReOpen(newindex,old[newindex].g,children[i].PrevMove);
				//}
				//else //(g in close is lower than g in children)
				//{
				//	if(old[newindex].g==children[i].g)
				//	{
				//	if(old[newindex].h<children[i].h)
				//	{
				//		boo=false;
				//		old[newindex].h=children[i].h;
				//		ReOpen(newindex,old[newindex].g,children[i].PrevMove);
				//	}
				//	}
				//}//---*********** this part worked ********************---
			}
}//end if (for existing child)
		else
			boo=true;
		//boo=true; //for testing
		if (boo) 
		{
			//printf("%s\n","adding the child");
			children[i].add2Open=true;
		}
		else
		{
			//printf("%s\n","NOT adding the child");
			children[i].add2Open=false;
		}

		
	//string mystr;
	//getline (cin,mystr);
	}//end for

	//After updating the children heuristic, need to find new maxH
	//maxH=0;
	//for (int i=0;i<ChildNum;i++)
	//{
	//	maxH=MAX(maxH,children[i].h-2);
	//}//end for

	//printf("%s\n","-- before insert to open --");
	// Now we can add the children to the OPEN list
	for (int i=0;i<ChildNum;i++)
	{
		if(children[i].add2Open)
		{
			//printf("%s %d\n","childh before change:",children[i].h);
			//children[i].h=MAX(maxH,children[i].h);
			//printf("%s %d\n","childh after change:",children[i].h);
			hashval=CalcHash(children[i].boardState);
			InsertHash2(children[i].boardState,hashval,children[i].PrevMove,children[i].g,children[i].h);

		}
	}//end for
	old[stateIndex].h=MAX(old[stateIndex].h,maxH-1);

return -1;

}

void BPMXAStar(short s[SIZE])
{
		//Variables
	int blank;
	int CurrentHashValue;
	int CurrentDepth;
	int CurrentOpenNode; //next node in the open list to check
	double startclock;
	double endclock;
	double innerclock;
	double time2loop;
	FILE *solution;

	//srand ( (unsigned)time ( NULL ) );

	//Init Hash table
	for (int i = 0; i< MAX; i++)                    /* empty hash table */
    {
		old[i].g = -1;                  /* only g value checked for emptiness */
		old[i].heaplink=-1;
		bucket[i] = MAX;
		for (int k=0;k<SIZE;k++)
			old[i].boardState[k]=-1;
	}

	for (int t=0;t<FULL;t++)
	{
		heap[t]=-1;
	}


	//Init Open List pointers
	OpenStart=0; // beginning of the open list
	OpenEnd = 0; //End of the open list

	//Init next free loaction index in hash table
	empty=0;

	//Init counters
	maxopen=0;
	copen=0;
	expanded=0;                               
	generated=0;                             
	stored=0;
	reopened=0;
	reclose=0;
	opened=0;
	closed=0;
	CurrentOpenNode=0;
	ImmediateGenerated=0;
	IE=0;
	UpperLimit=1101; //TODO - need to find logical upper limit
	FoundInC=0;
	FoundInO=0;
	sameV=0;

	//Init goal test inidicator
	CurrentDepth=0;
	//duplicateFlag = 1;
	duplicatCounter=0;
	goalDepth=0;
		//Start counting time
	startclock = (double)clock();
	CurrentHashValue=CalcHash(s);
	//Insert the initial state to the hash table and update the open list
	for (int word = 0;word<SIZE;word++)
		old[empty].boardState[word]=s[word];
	old[empty].PrevMove = SIZE;
	old[empty].g = 0;
	//ConvertStateToDual(0);
	old[empty].h=bestf=GetHuristicRegular(0,0);
	old[empty].link = bucket[CurrentHashValue];      /* next pointer to old first element */
	old[empty].heaplink=0;
	 bucket[CurrentHashValue] = empty;               /* new state is at head of hash chain */
	 int f = old[empty].g + old[empty].h; 
	empty++;
	heap[0]=0;

	while ( CurrentDepth!=100 && stored <FULL && OpenStart>=0)
	{
		//printf("%s\n","--Expand new node--");
		bestf=old[heap[0]].h+old[heap[0]].g;
		CurrentOpenNode=heap[0];
		//if(IsGoal(CurrentOpenNode))
		//{
		//	goalDepth=old[CurrentOpenNode].g;
		//	break;
		//}
		DeleteFromOpenList(CurrentOpenNode); //delete the node expanded from the open list
			
		CurrentDepth=BExpandNode(CurrentOpenNode,old[CurrentOpenNode].g,old[CurrentOpenNode].h,old[CurrentOpenNode].PrevMove);
		//CurrentDepth=BExpandNode(CurrentOpenNode,old[CurrentOpenNode].g,old[CurrentOpenNode].h,old[CurrentOpenNode].PrevMove);
		expanded++;
	}
//goalDepth=UpperLimit;
endclock = (double)clock();
	time2search = (endclock-startclock)/(double)CLOCKS_PER_SEC;
//	PrintResult2File("AStartLH",lookahead);
	PrintResult("A*+BPMX(1)");
	printf("%s","expanded= ");
	printf("%d \n",expanded);
	printf("%s","IE= ");
	printf("%d \n",IE);
	printf("%s","stored = ");
	printf("%d \n",stored);
		printf("%s","reopened = ");
	printf("%d \n",reopened);
		printf("%s","IG= ");
	printf("%d \n",ImmediateGenerated);
	printf("%s","opened = ");
		printf("%d \n",opened);
	printf("%s","closed = ");
	printf("%d \n",closed);
	printf("%s %d\n","maxopen = ",maxopen);
	printf("%s","goalDepth = ");
	printf("%d \n",goalDepth);
	printf("%s", "Start Time = ");
	printf ("%f \n",startclock);
	printf("%s", "Stop Time = ");
	printf ("%f \n",endclock);
	printf ("%s","sameV = ");
	printf ("%d \n",sameV);
	printf("%s", "time2search = ");
	printf ("%f \n",time2search);

}

int IBPMXExpand(int stateIndex,int g,int h, int PrevMove)
{
	 struct child
	 {                           
		 short boardState[SIZE];
		 short g;                                      /* distance from initial state */
		 short h;                        /* static heuristic distance from goal state */
		 short PrevMove;                                /* previous position of blank */
		 bool add2Open;
	 } children[SIZE];

	int blank;
	int newblank;
	int newindex;
	int opindex;

	int newg;
	int newh;
	int newf;
	int tile;
	int flag=-1;

	int hashval;
	int maxH;  //holds the maximum H between all immediate children
	int ChildNum;
	string mystr;

	FILE *solution;

	maxH=h-1;
	ChildNum=0;


	//printf("%s\n","generating children");
	newg=g+1;
	// Generate all the immediate children:
	for (int newMove = 0; newMove < SIZE; newMove++)
	{
		if (!OperMat[PrevMove][newMove])// 0 -> 4 -> 8
		 {
			 //printf("%s %d\n","not allowed move: ",opindex);
			continue;
		}

		MakeMove(stateIndex,newMove);
		//printf("%s","the child node is:");
		//for (int l=0;l<SIZE;l++)
		//	printf("%d ",old[stateIndex].boardState[l]);
		//printf("%s\n","");
		//ConvertStateToDual(stateIndex);
		newh=GetHuristicRegular(stateIndex,0);
		//printf("%s %d\n","child h=",newh);
		//getline (cin,mystr);
		maxH=MAX(maxH,newh-2);

		 newf=newh+newg;
		 //Add the child to the children list
		 for(int i=0;i<SIZE;i++)
			children[ChildNum].boardState[i]=old[stateIndex].boardState[i];
		 children[ChildNum].g=newg;
		 children[ChildNum].h=newh;
		 children[ChildNum].PrevMove=newMove;
		 if (IsGoal(children[ChildNum].boardState))	
		 {
			 if(UpperLimit>children[ChildNum].g)
				 UpperLimit=children[ChildNum].g;
			 //printf("%s %d\n","goal depth=", UpperLimit);
		 }
		 generated++;
		 ChildNum++;
		 
		 MakeMove(stateIndex,newMove);
		 
		// printf("%s","state after undo:");
		//for (int l=0;l<SIZE;l++)
		//	printf("%d ",old[stateIndex].boardState[l]);
		//printf("%s\n","");
	}
	
	


	//printf("%s %d\n","maxh=",maxH);
	//Now, update the children heuristic based on maxH found:
	for (int i=0;i<ChildNum;i++)
	{
		//printf("%s %d\n","child h before change:",children[i].h);
		children[i].h=MAX(maxH,children[i].h);
		///printf("%s %d\n","child h after change1:",children[i].h);
		//if(children[i].g+children[i].h<old[stateIndex].g+old[stateIndex].h)
		//if(children[i].g+children[i].h<g+h)
			//children[i].h=old[stateIndex].h-1;
			//children[i].h=h-1;
		//printf("%s %d\n","child h after change2:",children[i].h);

		//Search for the child in memory
		hashval=CalcHash(children[i].boardState);
		newindex=SearchHash(children[i].boardState,hashval);
		if(newindex==stateIndex) newindex=-1;
		//printf("%s %d\n","newindex=",newindex);

		//if(newindex!=-1 && old[newindex].PrevMove!=children[i].PrevMove)
		//{
		//	printf("%s\n","different prev moves");
		//string mystr;
		//getline (cin,mystr);
		//}
		//printf("%s %d\n","newindex=",newindex);

		
		short boo=0; //0 - add new; 1 - don't add old; 2 - reopen (already appear in open)
		// if the state already exists
		if(newindex!=-1)
		{
			
			//Check if exists in close list
			if(old[newindex].heaplink==-1)
			{
				//printf("%s","Found the state in close ");
				//for(int j=0;j<SIZE;j++)
				//	printf("%d ",old[newindex].boardState[j]);
				//printf("%s %d %s %d\n","h=",old[newindex].h," g=",old[newindex].g);
				//printf("%s %d %s %d\n","childh=",children[i].h," chilg=",children[i].g);
				//string mystr;
				//getline (cin,mystr);
				FoundInC++;
				//if(old[newindex].h>children[i].h)
				//{
				//	children[i].h=old[newindex].h;
				//	UpdateH=true;
				//}
				if(old[newindex].g<=children[i].g)
				{
					boo=1;
					//if(old[newindex].h>=children[i].h)
					//boo=false;

				}
				//else
				//if(old[newindex].g==children[i].g && old[newindex].h>=children[i].h)
				//		boo=false;
				//if(boo) //(g in close is lower than g in children)
				else
				{
						boo=0;
						//for (int j=0;j<SIZE;j++)
						//old[newindex].boardState[j]=-1;
					old[newindex].h=-1;
					old[newindex].g=-1;
				}
				
			}// end if - if in close list
		
			//else //the node is in the open list
			if(old[newindex].heaplink!=-1)
			{
				//printf("%s","Found the state in close ");
				//for(int j=0;j<SIZE;j++)
				//	printf("%d ",old[newindex].boardState[j]);
				//printf("%s %d %s %d\n","h=",old[newindex].h," g=",old[newindex].g);
				//printf("%s %d %s %d\n","childh=",children[i].h," chilg=",children[i].g);
				//string mystr;
				//getline (cin,mystr);
				boo=1;
				FoundInO++;

				//if(old[newindex].h>children[i].h)
				//	children[i].h=old[newindex].h;
				if(old[newindex].g>children[i].g)
				{
					//old[newindex].g=children[i].g;
					boo=2;
					if(old[newindex].h<children[i].h)
						old[newindex].h=children[i].h;
					maxH=MAX(maxH,old[newindex].h-2);
					//ReOpen(newindex,children[i].g,children[i].PrevMove);
				}

				//---*********** this part worked ********************---
				//if(old[newindex].g>children[i].g)
				//{
				//	old[newindex].g=children[i].g;
				//	boo=false;
				//	if(old[newindex].h<children[i].h)
				//		old[newindex].h=children[i].h;
				//	ReOpen(newindex,old[newindex].g,children[i].PrevMove);
				//}
				//else //(g in close is lower than g in children)
				//{
				//	if(old[newindex].g==children[i].g)
				//	{
				//	if(old[newindex].h<children[i].h)
				//	{
				//		boo=false;
				//		old[newindex].h=children[i].h;
				//		ReOpen(newindex,old[newindex].g,children[i].PrevMove);
				//	}
				//	}
				//}//---*********** this part worked ********************---
			}
}//end if (for existing child)
		else
			boo=0;
		//boo=true; //for testing
		if (boo==0) 
		{
			//printf("%s\n","adding the child");
			children[i].add2Open=true;
		}
		if(boo==1)
		{
			//printf("%s\n","NOT adding the child");
			children[i].add2Open=false;
		}
		if(boo==2)
		{
			ReOpen(newindex,children[i].g,children[i].PrevMove);
			children[i].add2Open=false;
		}

		
	//string mystr;
	//getline (cin,mystr);
	}//end for


	//After updating the children heuristic, need to find new maxH
	//maxH=0;
	//for (int i=0;i<ChildNum;i++)
	//{
	//	maxH=MAX(maxH,children[i].h-2);
	//}//end for

	//printf("%s\n","-- before insert to open --");
	// Now we can add the children to the OPEN list
	for (int i=0;i<ChildNum;i++)
	{
		if(children[i].add2Open)
		{
			//printf("%s %d\n","childh before change:",children[i].h);
			//children[i].h=MAX(maxH,children[i].h);
			//printf("%s %d\n","childh after change:",children[i].h);
			//printf("%s","Child to insert:");
			//for (int j=0;j<SIZE;j++)
			//	printf("%d ",children[i].boardState[j]);
			//printf("%s\n","");
			//getline (cin,mystr);
			hashval=CalcHash(children[i].boardState);
			if(children[i].h+children[i].g<UpperLimit)
			{
			//if(children[i].h+children[i].g>old[heap[0]].g+old[heap[0]].h)
			if(children[i].h+children[i].g>NextBestF) 
			{
			//solution=fopen("solution_1.txt","a");
			//fprintf(solution,"%s ","co,");
			//for (int j=0;j<SIZE;j++)
			//	fprintf(solution,"%d ",children[i].boardState[j]);
			//fprintf(solution,",%d,%d,%d,",children[i].g,children[i].h,old[heap[0]].g+old[heap[0]].h);
			////for (int s=0;s<OpenStart;s++)
			//// {
			////	fprintf(solution,"%d %s %d ",old[heap[s]].g+old[heap[s]].h,"->",old[heap[s]].g);
			//// }
			//fprintf(solution,"%s\n","");
			//fclose(solution);
				//printf("%s\n","inserting to OPEN");
				InsertHash2(children[i].boardState,hashval,children[i].PrevMove,children[i].g,children[i].h);
			}
			else
			{
				//printf("%s\n","inserting to CLOSE");
				//printf("%s %d %s %d\n","childf=",children[i].h+children[i].g," parentf=",old[heap[0]].g+old[heap[0]].h);
				//getline (cin,mystr);
			//solution=fopen("solution_1.txt","a");
			//fprintf(solution,"%s ","cc,");
			//for (int j=0;j<SIZE;j++)
			//	fprintf(solution,"%d ",children[i].boardState[j]);
			//	fprintf(solution,",%d,%d,%d,\n",children[i].g,children[i].h,old[heap[0]].g+old[heap[0]].h);
			//	fclose(solution);
				
				int hashindex=Add2Close(children[i].boardState,hashval,children[i].PrevMove,children[i].g,children[i].h);
						IE++;
					IBPMXExpand(hashindex,children[i].g,children[i].h,children[i].PrevMove);
					
				
			}

			}
		}
	}//end for
	old[stateIndex].h=MAX(old[stateIndex].h,maxH-1);

return -1;

}

int IIBExpandNode(int stateIndex,int g,int h, int PrevMove)
{
	 struct child
	 {                           
		 short boardState[SIZE];
		 short g;                                      /* distance from initial state */
		 short h;                        /* static heuristic distance from goal state */
		 short PrevMove;                                /* previous position of blank */
		 bool add2Open;
	 } children[SIZE];

	int blank;
	int newblank;
	int newindex;
	int opindex;

	int newg;
	int newh;
	int newf;
	int tile;
	int flag=-1;

	int hashval;
	int maxH;  //holds the maximum H between all immediate children
	int ChildNum;

	FILE *solution;

	//maxH=0;
	maxH=h-1;
	ChildNum=0;

	// First check if the state is the goal
	//printf("%s","checking for goal:");
	//for (int i=0;i<SIZE;i++)
	//	printf("%d ",old[stateIndex].boardState[i]);
	//printf("%s\n","");
	//if(IsGoal(stateIndex))
	//{
	//			printf("%s\n","found goal");
	//	for(int i=0;i<SIZE;i++)
	//		printf("%d ",old[stateIndex].boardState[i]);
	//	printf("%s\n","");
	//	goalDepth=old[stateIndex].g;
	//	return 100;
	//}

	//printf("%s\n","generating children");
	// Generate all the immediate children:
	newg=g+1;
	for (int newMove = 0; newMove < SIZE; newMove++)
	{
		if (!OperMat[PrevMove][newMove])// 0 -> 4 -> 8
		 {
			 //printf("%s %d\n","not allowed move: ",opindex);
			continue;
		}

		//newblank=opindex;
		MakeMove(stateIndex,newMove);
		if(IsGoal(stateIndex))
		{
			if(UpperLimit>newg) UpperLimit=newg;
		}
		//printf("%s","the child node is:");
		//for (int l=0;l<SIZE;l++)
		//	printf("%d ",old[stateIndex].boardState[l]);
		//ConvertStateToDual(stateIndex);
		newh=GetHuristicRegular(stateIndex,0);
		//printf("%s %d\n","child h=",newh);
		maxH=MAX(maxH,newh-2);

		 

		 newf=newh+newg;
		 //Add the child to the children list
		 for(int i=0;i<SIZE;i++)
			children[ChildNum].boardState[i]=old[stateIndex].boardState[i];
		 children[ChildNum].add2Open=false;
		 children[ChildNum].g=newg;
		 children[ChildNum].h=newh;
		 children[ChildNum].PrevMove=newMove;
		 generated++;
		 ChildNum++;
		 MakeMove(stateIndex,newMove);
		// printf("%s","state after undo:");
		//for (int l=0;l<SIZE;l++)
		//	printf("%d ",old[stateIndex].boardState[l]);
		//printf("%s\n","");
	}
	//string mystr;
	//getline (cin,mystr);


	//printf("%s %d\n","maxh=",maxH);
	//Now, update the children heuristic based on maxH found:
	for (int i=0;i<ChildNum;i++)
	{
		//printf("%s %d\n","child h before change:",children[i].h);
		children[i].h=MAX(maxH,children[i].h);
		///printf("%s %d\n","child h after change1:",children[i].h);
		//if(children[i].g+children[i].h<old[stateIndex].g+old[stateIndex].h)
		//	children[i].h=old[stateIndex].h-1;
		//printf("%s %d\n","child h after change2:",children[i].h);

		//Search for the child in memory
		hashval=CalcHash(children[i].boardState);
		newindex=SearchHash(children[i].boardState,hashval);
		if(newindex==stateIndex) newindex=-1;
		//if(newindex!=-1 && old[newindex].PrevMove!=children[i].PrevMove)
		//{
		//	printf("%s\n","different prev moves");
		//string mystr;
		//getline (cin,mystr);
		//}
		//printf("%s %d\n","newindex=",newindex);

		bool boo=true;
		// if the state already exists
		if(newindex!=-1)
		{
			
			//Check if exists in close list
			if(old[newindex].heaplink==-1)
			{
				//printf("%s","Found the state in close ");
				//for(int j=0;j<SIZE;j++)
				//	printf("%d ",old[newindex].boardState[j]);
				//printf("%s %d %s %d\n","h=",old[newindex].h," g=",old[newindex].g);
				//printf("%s %d %s %d\n","childh=",children[i].h," chilg=",children[i].g);
				//string mystr;
				//getline (cin,mystr);
				FoundInC++;
				//if(old[newindex].h>children[i].h)
				//{
				//	children[i].h=old[newindex].h;
				//	UpdateH=true;
				//}
				if(old[newindex].g<=children[i].g)
				{
					boo=false;
					//if(old[newindex].h>=children[i].h)
					//boo=false;

				}
				//else
				//if(old[newindex].g==children[i].g && old[newindex].h>=children[i].h)
				//		boo=false;
				//if(boo) //(g in close is lower than g in children)
				else
				{
					reclose++;
						boo=true;
						for (int j=0;j<SIZE;j++)
						old[newindex].boardState[j]=-1;
					old[newindex].h=-1;
					old[newindex].g=-1;
				}
				
			}// end if - if in close list
		
			//else //the node is in the open list
			if(old[newindex].heaplink!=-1)
			{
				//printf("%s","Found the state in close ");
				//for(int j=0;j<SIZE;j++)
				//	printf("%d ",old[newindex].boardState[j]);
				//printf("%s %d %s %d\n","h=",old[newindex].h," g=",old[newindex].g);
				//printf("%s %d %s %d\n","childh=",children[i].h," chilg=",children[i].g);
				//string mystr;
				//getline (cin,mystr);
				boo=false;
				FoundInO++;

				//if(old[newindex].h>children[i].h)
				//	children[i].h=old[newindex].h;
				if(old[newindex].g>children[i].g)
				{
					//old[newindex].g=children[i].g;
					reopened++;
					boo=false;
					if(old[newindex].h<children[i].h)
						old[newindex].h=children[i].h;
					ReOpen(newindex,children[i].g,children[i].PrevMove);
				}

				//---*********** this part worked ********************---
				//if(old[newindex].g>children[i].g)
				//{
				//	old[newindex].g=children[i].g;
				//	boo=false;
				//	if(old[newindex].h<children[i].h)
				//		old[newindex].h=children[i].h;
				//	ReOpen(newindex,old[newindex].g,children[i].PrevMove);
				//}
				//else //(g in close is lower than g in children)
				//{
				//	if(old[newindex].g==children[i].g)
				//	{
				//	if(old[newindex].h<children[i].h)
				//	{
				//		boo=false;
				//		old[newindex].h=children[i].h;
				//		ReOpen(newindex,old[newindex].g,children[i].PrevMove);
				//	}
				//	}
				//}//---*********** this part worked ********************---
			}
}//end if (for existing child)
		else
			boo=true;
		//boo=true; //for testing
		if (boo) 
		{
			//printf("%s\n","adding the child");
			children[i].add2Open=true;
		}
		else
		{
			//printf("%s\n","NOT adding the child");
			children[i].add2Open=false;
		}

		
	//string mystr;
	//getline (cin,mystr);
	}//end for

	//After updating the children heuristic, need to find new maxH
	//maxH=0;
	//for (int i=0;i<ChildNum;i++)
	//{
	//	maxH=MAX(maxH,children[i].h-2);
	//}//end for

	//printf("%s\n","-- before insert to open --");
	// Now we can add the children to the OPEN list
	for (int i=0;i<ChildNum;i++)
	{
		if(CostArr[children[i].h+children[i].g]==-1) CostArr[children[i].h+children[i].g]=1;
		if(children[i].add2Open)
		{
			if(children[i].h+children[i].g<UpperLimit)
			{
			//printf("%s %d\n","childh before change:",children[i].h);
			//children[i].h=MAX(maxH,children[i].h);
			//printf("%s %d\n","childh after change:",children[i].h);
				hashval=CalcHash(children[i].boardState);
				if(children[i].h+children[i].g<=NextBestF)
				{
					IE++;
					int cindex=Add2Close(children[i].boardState,hashval,children[i].PrevMove,children[i].g,children[i].h);
					IIBExpandNode(cindex,children[i].g,children[i].h,children[i].PrevMove);
				}
				else
				{
					
					InsertHash2(children[i].boardState,hashval,children[i].PrevMove,children[i].g,children[i].h);
				}
			}

		}
	}//end for
	old[stateIndex].h=MAX(old[stateIndex].h,maxH-1);

return -1;

}

void IBPMXAStar(short s[SIZE])
{
		//Variables
	int blank;
	int CurrentHashValue;
	int CurrentDepth;
	int CurrentOpenNode; //next node in the open list to check
	double startclock;
	double endclock;
	double innerclock;
	double time2loop;
	FILE *solution;

	//srand ( (unsigned)time ( NULL ) );

	//Init Hash table
	for (int i = 0; i< MAX; i++)                    /* empty hash table */
    {
		old[i].g = -1;                  /* only g value checked for emptiness */
		old[i].heaplink=-1;
		bucket[i] = MAX;
		for (int k=0;k<SIZE;k++)
			old[i].boardState[k]=-1;
	}

	for (int t=0;t<FULL;t++)
	{
		heap[t]=-1;
	}


	//Init Open List pointers
	OpenStart=0; // beginning of the open list
	OpenEnd = 0; //End of the open list

	//Init next free loaction index in hash table
	empty=0;

	//Init counters
	maxopen=0;
	copen=0;
	expanded=0;                               
	generated=0;                             
	stored=0;
	reopened=0;
	reclose=0;
	opened=0;
	closed=0;
	CurrentOpenNode=0;
	ImmediateGenerated=0;
	IE=0;
	UpperLimit=1101; //TODO - need to find logical upper limit
	FoundInC=0;
	FoundInO=0;

	//Init goal test inidicator
	CurrentDepth=0;
	//duplicateFlag = 1;
	duplicatCounter=0;
	goalDepth=0;
	NextBestF=0;
		//Start counting time
	startclock = (double)clock();
	CurrentHashValue=CalcHash(s);
	//Insert the initial state to the hash table and update the open list
	for (int word = 0;word<SIZE;word++)
		old[empty].boardState[word]=s[word];
	old[empty].PrevMove = SIZE;
	old[empty].g = 0;
	//ConvertStateToDual(0);
	old[empty].h=bestf=GetHuristicRegular(0,0);
	old[empty].link = bucket[CurrentHashValue];      /* next pointer to old first element */
	old[empty].heaplink=0;
	 bucket[CurrentHashValue] = empty;               /* new state is at head of hash chain */
	 int f = old[empty].g + old[empty].h; 
	empty++;
	heap[0]=0;

	while (CurrentDepth!=100 && old[heap[0]].h+old[heap[0]].g<UpperLimit && stored <FULL && OpenStart>=0)
	{
			//solution=fopen("solution_1.txt","a");
			//fprintf(solution,"%s ","e,");
			//for (int j=0;j<SIZE;j++)
			//	fprintf(solution,"%d ",old[heap[0]].boardState[j]);
			//	fprintf(solution,",%d,%d,%d,\n",old[heap[0]].g,old[heap[0]].h,UpperLimit);
			//	fclose(solution);
		//printf("%s\n","--Expand new node--");
		bestf=old[heap[0]].h+old[heap[0]].g;
		CurrentOpenNode=heap[0];
		if(IsGoal(CurrentOpenNode))
		{
			goalDepth=old[CurrentOpenNode].g;
			break;
		}
		DeleteFromOpenList(CurrentOpenNode); //delete the node expanded from the open list
			
		NextBestF=old[CurrentOpenNode].h+old[CurrentOpenNode].g;
		//CurrentDepth=IBPMXExpand(CurrentOpenNode,old[CurrentOpenNode].g,old[CurrentOpenNode].h,old[CurrentOpenNode].PrevMove);
		CurrentDepth=IIBExpandNode(CurrentOpenNode,old[CurrentOpenNode].g,old[CurrentOpenNode].h,old[CurrentOpenNode].PrevMove);
		//CurrentDepth=BExpandNode(CurrentOpenNode,old[CurrentOpenNode].g,old[CurrentOpenNode].h,old[CurrentOpenNode].PrevMove);
		expanded++;
	}
	//printf("%s %d %s %d\n","old[heap[0]].h=",old[heap[0]].h," old[heap[0]].g=",old[heap[0]].g);
goalDepth=UpperLimit;
endclock = (double)clock();
	time2search = (endclock-startclock)/(double)CLOCKS_PER_SEC;
//	PrintResult2File("AStartLH",lookahead);
	PrintResult("IA*+BPMX(1)");
	printf("%s","expanded= ");
	printf("%d \n",expanded);
	printf("%s","IE= ");
	printf("%d \n",IE);
	printf("%s","stored = ");
	printf("%d \n",stored);
		printf("%s","reopened = ");
	printf("%d \n",reopened);
		printf("%s","IG= ");
	printf("%d \n",ImmediateGenerated);
	printf("%s","opened = ");
		printf("%d \n",opened);
	printf("%s","closed = ");
	printf("%d \n",closed);
	printf("%s %d\n","maxopen = ",maxopen);
	printf("%s","goalDepth = ");
	printf("%d \n",goalDepth);
	printf("%s", "Start Time = ");
	printf ("%f \n",startclock);
	printf("%s", "Stop Time = ");
	printf ("%f \n",endclock);
	printf ("%s","Duplicated = ");
	printf ("%d \n",duplicatCounter);
	printf("%s", "time2search = ");
	printf ("%f \n",time2search);

}




int HBLookahead(int stateIndex,int g, int h, int lookahead, int PrevMove)
{
	int opindex;
	int newblank;
	int newg;
	int newh;
	int rh;
	int maxH;



	rh=0;
	maxH=0;
	//printf("%s %d %s %d\n","lookahead=",lookahead,"g=",g);

	if (IsGoal(stateIndex))
	{
		if (g<UpperLimit) UpperLimit=g;
		//printf("%s %d\n","goal depth is: ",UpperLimit);
		//printf("%s %d %s %d\n","ph1=",old[stateIndex].h," pg=",old[stateIndex].g);
		//return -1; //do we need it? I think we do otherwise it will continue on
		return g;
	}



	if (h+g>lookahead)
	{
		//printf("%s\n","f bigger than lookahead, returning h");
		//for(int i=0;i<SIZE;i++)
		//	printf("%d ",old[stateIndex].boardState[i]);
		//printf("%s %d\n","h=",h);
		//printf("%s\n","");
		return h;//return 1000; // the cost is higher than the lookahead level - need to rollback
	}
	//if (IsGoal(stateIndex))
	//{
	//	//for (int k=0;k<SIZE;k++)
	//		//printf("%d ",old[stateIndex].boardState[k]);
	//	if (g<UpperLimit) UpperLimit=g;
	//	printf("%s %d %s %d %s %d %s %d\n","goal depth is: ",UpperLimit,"parent f=",old[stateIndex].h+old[stateIndex].g," lookahead=",lookahead,"stateIndex=",stateIndex);
	//	return g;
	//}


	//if the cost is lower than lookahead and the state is not goal - need to develope its children
	newg=g+1; // calculate child g
	for (int newMove = 0; newMove < SIZE; newMove++)
	{
		if (!OperMat[PrevMove][newMove])// 0 -> 4 -> 8
		 {
			 //printf("%s %d\n","not allowed move: ",opindex);
			continue;
		}


		MakeMove(stateIndex,newMove); //generate a child
		//printf("%s","Goining deeper: ");
		//for (int i=0;i<SIZE;i++)
		//	 printf("%d ",old[stateIndex].boardState[i]);
		//printf("%s\n","");
		//if(IsGoal(stateIndex)) printf("%s %d\n","goal depht is-->>", newg);

		 ImmediateGenerated++;

		 //ConvertStateToDual(stateIndex);
		 newh=GetHuristicRegular(stateIndex,0); //calculate child h
		 //printf("%s %d %s %d\n","newh=",newh,"newg=",newg);
		 //if(newh-h>1 || newh-h<-1) {printf("%s %d %s %d\n","----->>>>>found inconsistency! newh=",newh," h=",h);
		 //	string mystr;
			//getline (cin,mystr);}

		 
		 if( newg+newh<UpperLimit ) // if the child cost is lower than the current goal - perform DFS
		 {
			 rh=HBLookahead(stateIndex,newg,newh,lookahead,newMove);
		 }

		 MakeMove(stateIndex,newMove);
		 //printf("%s %d\n","h before update:",h);
		 h=MAX(h,rh-1);
		 //printf("%s %d\n","h after update:",h);
		 if(g+h>lookahead)
		 {
			 //printf("%s %d %s %d %s %d %s %d\n","h after update=",h," g=",g," newg=",newg, " lookahead=",lookahead);
			 return h;
		 }
		 	 
		 		 
	}//end for

return h;
}//End BLookahead

int ILHBPMXExpand(int stateIndex,int g,int h, int lookahead,int PrevMove)
{
	 struct child
	 {                           
		 short boardState[SIZE];
		 short g;                                      /* distance from initial state */
		 short h;                        /* static heuristic distance from goal state */
		 short PrevMove;                                /* previous position of blank */
		 bool add2Open;
	 } children[SIZE];

	int blank;
	int newblank;
	int newindex;
	int opindex;

	int newg;
	int newh;
	int newf;
	int tile;
	int flag=-1;

	int hashval;
	int maxH;  //holds the maximum H between all immediate children
	int ChildNum;
	string mystr;

	FILE *solution;

	//int LHResult=HBLookahead(stateIndex,g,h,lookahead,PrevMove);
	maxH=h-1;
	ChildNum=0;


	//printf("%s\n","generating children");
	newg=g+1;
	// Generate all the immediate children:
	for (int newMove = 0; newMove < SIZE; newMove++)
	{
		if (!OperMat[PrevMove][newMove])// 0 -> 4 -> 8
		 {
			 //printf("%s %d\n","not allowed move: ",opindex);
			continue;
		}

		MakeMove(stateIndex,newMove);
		//printf("%s","the child node is:");
		//for (int l=0;l<SIZE;l++)
		//	printf("%d ",old[stateIndex].boardState[l]);
		//printf("%s\n","");
		//ConvertStateToDual(stateIndex);
		newh=GetHuristicRegular(stateIndex,0);
		//printf("%s %d\n","child h=",newh);
		//getline (cin,mystr);
		maxH=MAX(maxH,newh-2);

		 newf=newh+newg;
		 //Add the child to the children list
		 for(int i=0;i<SIZE;i++)
			children[ChildNum].boardState[i]=old[stateIndex].boardState[i];
		 children[ChildNum].g=newg;
		 children[ChildNum].h=newh;
		 children[ChildNum].PrevMove=newMove;
		 if (IsGoal(children[ChildNum].boardState))	
		 {
			 if(UpperLimit>children[ChildNum].g)
				 UpperLimit=children[ChildNum].g;
			// printf("%s %d %s %d %s %d %s %d\n","goal depth=", UpperLimit,"ph=",h,"pg=",g,"lookahead=",lookahead);
		 }
		 children[ChildNum].add2Open=false;
		 generated++;
		 ChildNum++;
		 
		 MakeMove(stateIndex,newMove);
		 
		// printf("%s","state after undo:");
		//for (int l=0;l<SIZE;l++)
		//	printf("%d ",old[stateIndex].boardState[l]);
		//printf("%s\n","");
	}
	
	


	//printf("%s %d\n","maxh=",maxH);
	//Now, update the children heuristic based on maxH found:
	for (int i=0;i<ChildNum;i++)
	{
		//printf("%s %d\n","child h before change:",children[i].h);
		children[i].h=MAX(maxH,children[i].h);
		if(children[i].h+children[i].g<UpperLimit)
		{
			if(children[i].h+children[i].g>=UpperLimit) printf("%s\n","extra");
			///printf("%s %d\n","child h after change1:",children[i].h);

			//Search for the child in memory
			hashval=CalcHash(children[i].boardState);
			newindex=SearchHash(children[i].boardState,hashval);
			if(newindex==stateIndex) newindex=-1;
			//printf("%s %d\n","newindex=",newindex);

		
			short boo=0; //0 - add new; 1 - don't add old; 2 - reopen (already appear in open)
			// if the state already exists
			if(newindex!=-1)
			{
			
				//Check if exists in close list
				if(old[newindex].heaplink==-1)
				{
					//printf("%s","Found the state in close ");
					//for(int j=0;j<SIZE;j++)
					//	printf("%d ",old[newindex].boardState[j]);
					//printf("%s %d %s %d\n","h=",old[newindex].h," g=",old[newindex].g);
					//printf("%s %d %s %d\n","childh=",children[i].h," chilg=",children[i].g);
					//string mystr;
					//getline (cin,mystr);
					FoundInC++;
					//if(old[newindex].h>children[i].h)
					//{
					//	children[i].h=old[newindex].h;
					//	UpdateH=true;
					//}
					if(old[newindex].g<=children[i].g)
					{
						boo=1;
						//if(old[newindex].h>=children[i].h)
						//boo=false;

					}
					//else
					//if(old[newindex].g==children[i].g && old[newindex].h>=children[i].h)
					//		boo=false;
					//if(boo) //(g in close is lower than g in children)
					else
					{
							boo=0;
						for (int j=0;j<SIZE;j++)
							old[newindex].boardState[j]=-1;
						old[newindex].h=-1;
						old[newindex].g=-1;
					}
					
				}// end if - if in close list
		
				//else //the node is in the open list
				if(old[newindex].heaplink!=-1)
				{
					boo=1;
					FoundInO++;
					if(old[newindex].g>children[i].g)
					{
						//old[newindex].g=children[i].g;
						boo=2;
						if(old[newindex].h<children[i].h)
						old[newindex].h=children[i].h;
						maxH=MAX(maxH,old[newindex].h-2);
						//ReOpen(newindex,children[i].g,children[i].PrevMove);
					}

				//---*********** this part worked ********************---
				//if(old[newindex].g>children[i].g)
				//{
				//	old[newindex].g=children[i].g;
				//	boo=false;
				//	if(old[newindex].h<children[i].h)
				//		old[newindex].h=children[i].h;
				//	ReOpen(newindex,old[newindex].g,children[i].PrevMove);
				//}
				//else //(g in close is lower than g in children)
				//{
				//	if(old[newindex].g==children[i].g)
				//	{
				//	if(old[newindex].h<children[i].h)
				//	{
				//		boo=false;
				//		old[newindex].h=children[i].h;
				//		ReOpen(newindex,old[newindex].g,children[i].PrevMove);
				//	}
				//	}
				//}//---*********** this part worked ********************---
				}
	}//end if (for existing child)
			else
				boo=0;
		//boo=true; //for testing
		if (boo==0) 
		{
			//printf("%s\n","adding the child");
			children[i].add2Open=true;
		}
		if(boo==1)
		{
			//printf("%s\n","NOT adding the child");
			children[i].add2Open=false;
		}
		if(boo==2)
		{
			ReOpen(newindex,children[i].g,children[i].PrevMove);
			children[i].add2Open=false;
		}

		}
	//string mystr;
	//getline (cin,mystr);
	}//end for


	//After updating the children heuristic, need to find new maxH
	//maxH=0;
	//for (int i=0;i<ChildNum;i++)
	//{
	//	maxH=MAX(maxH,children[i].h-2);
	//}//end for

	//printf("%s\n","-- before insert to open --");
	// Now we can add the children to the OPEN list
	for (int i=0;i<ChildNum;i++)
	{
		if(children[i].add2Open)
		{
			//printf("%s %d\n","childh before change:",children[i].h);
			//children[i].h=MAX(maxH,children[i].h);
			//printf("%s %d\n","childh after change:",children[i].h);
			//printf("%s","Child to insert:");
			//for (int j=0;j<SIZE;j++)
			//	printf("%d ",children[i].boardState[j]);
			//printf("%s\n","");
			//getline (cin,mystr);
			hashval=CalcHash(children[i].boardState);
			if(children[i].h+children[i].g<UpperLimit)
			{
			//if(children[i].h+children[i].g>old[heap[0]].g+old[heap[0]].h)
			if(children[i].h+children[i].g>NextBestF) 
			{
			//solution=fopen("solution_1.txt","a");
			//fprintf(solution,"%s ","co,");
			//for (int j=0;j<SIZE;j++)
			//	fprintf(solution,"%d ",children[i].boardState[j]);
			//fprintf(solution,",%d,%d,%d,",children[i].g,children[i].h,old[heap[0]].g+old[heap[0]].h);
			////for (int s=0;s<OpenStart;s++)
			//// {
			////	fprintf(solution,"%d %s %d ",old[heap[s]].g+old[heap[s]].h,"->",old[heap[s]].g);
			//// }
			//fprintf(solution,"%s\n","");
			//fclose(solution);
				//printf("%s\n","inserting to OPEN");
				InsertHash2(children[i].boardState,hashval,children[i].PrevMove,children[i].g,children[i].h);
			}
			else
			{
				//printf("%s\n","inserting to CLOSE");
				//printf("%s %d %s %d\n","childf=",children[i].h+children[i].g," parentf=",old[heap[0]].g+old[heap[0]].h);
				//getline (cin,mystr);
			//solution=fopen("solution_1.txt","a");
			//fprintf(solution,"%s ","cc,");
			//for (int j=0;j<SIZE;j++)
			//	fprintf(solution,"%d ",children[i].boardState[j]);
			//	fprintf(solution,",%d,%d,%d,\n",children[i].g,children[i].h,old[heap[0]].g+old[heap[0]].h);
			//	fclose(solution);
				int hashindex=Add2Close(children[i].boardState,hashval,children[i].PrevMove,children[i].g,children[i].h);
				//int result=HBLookahead(hashindex,children[i].g,children[i].h,lookahead,children[i].PrevMove);
				//children[i].h=MAX(children[i].h,result);
						IE++;
				if(children[i].h+children[i].g<=lookahead)
					ILHBPMXExpand(hashindex,children[i].g,children[i].h,lookahead,children[i].PrevMove);
					
				
			}

			}
		}
	}//end for
	old[stateIndex].h=MAX(old[stateIndex].h,maxH-1);

return -1;

}

int oHBLookahead3(short state[SIZE],int g, int h, int lookahead, int PrevMove)
{
	int opindex;
	int newblank;
	int newg;
	int newh;
	int rh;
	int maxH;



	rh=0;


	//printf("%s","Parent array:");
	//for (int i=0;i<SIZE;i++)
	//	printf("%d ",state[i]);
	//printf("%s\n","");
	//if the cost is lower than lookahead and the state is not goal - need to develope its children
	newg=g+1; // calculate child g
	for (int newMove = 0; newMove < SIZE; newMove++)
	{
		if (!OperMat[PrevMove][newMove])// 0 -> 4 -> 8
		 {
			 //printf("%s %d\n","not allowed move: ",opindex);
			continue;
			}


		MakeMove(state,newMove); //generate a child
		//printf("%s","Goining deeper: ");
		//for (int i=0;i<SIZE;i++)
		//	 printf("%d ",old[stateIndex].boardState[i]);
		//printf("%s\n","");
		//if(IsGoal(stateIndex)) printf("%s %d\n","goal depht is-->>", newg);

		 ImmediateGenerated++;

		 //ConvertStateToDual(state);
		 newh=GetHuristicRegular(state,0); //calculate child h
		 if(newh+newg<=lookahead && newh==0 && IsGoal(state))
		 {
			 if(newg<UpperLimit) UpperLimit=newg;
			 printf("%s %d\n","Found Goal==>>",UpperLimit);
			 MakeMove(state,newMove);
			 continue;
		 }
		 
		
		 	//string mystr;
			//getline (cin,mystr);

		// printf("%s %d %s %d %s %d\n","newh=",newh,"newg=",newg,"lookahead=",lookahead);
		 if( newg+newh<=lookahead && newg+newh<UpperLimit) // if the child cost is lower than the current goal - perform DFS
		 {
			 //rh=HBLookahead3(stateIndex,newg,newh,lookahead,newMove);
			 newh=oHBLookahead3(state,newg,newh,lookahead,newMove);
			// printf("%s %d\n","getting h:",newh);
		 }
		// printf("%s %d\n","after newh=",newh);
		 
		// else
		// {
		  //printf("%s %d\n","h before change:",h);
			 h=MAX(h,newh-1);
			 //	printf("%s","child to change array:");
				//for (int i=0;i<SIZE;i++)
				//	printf("%d ",old[stateIndex].boardState[i]);
				//printf("%s\n","");
			 MakeMove(state,newMove);
			// printf("%s","Changed to-->> array:");
			//for (int i=0;i<SIZE;i++)
			//	printf("%d ",old[stateIndex].boardState[i]);
			//printf("%s\n","");
			//string mystr;
			//getline (cin,mystr);
			
			 //h=MAX(h,rh-1);
			// printf("%s %d\n","h after change:",h);
			// string mystr;
			// getline (cin,mystr);
			 if(newh+newg<minf && newh+newg>lookahead) minf=newh+newg;
			 if(g+h>lookahead)
			 {
				 //printf("%s %d\n","sending h:",h);
				 return h;
			 }
		// }
		//MakeMove(stateIndex,newMove);
		 

		 //printf("%s %d\n","h before update:",h);

		 	 
		 		 
	}//end for

return h;
}//End BLookahead

int oIIBExpandNodeLH(int stateIndex,int g,int h, int PrevMove,int lookahead)
{
	 struct child
	 {                           
		 short boardState[SIZE];
		 //int boardState[SIZE];
		 short g;                                      /* distance from initial state */
		 short h;                        /* static heuristic distance from goal state */
		 int cost;
		 short PrevMove;                                /* previous position of blank */
		 bool add2Open;
	 } children[SIZE];

	int blank;
	int newblank;
	int newindex;
	int opindex;

	int newg;
	int newh;
	int newf;
	int tile;
	int flag=-1;

	int hashval;
	int maxH;  //holds the maximum H between all immediate children
	int ChildNum;

	FILE *solution;

	//maxH=0;
	maxH=h-1;
	ChildNum=0;

	// First check if the state is the goal
	//printf("%s","checking for goal:");
	//for (int i=0;i<SIZE;i++)
	//	printf("%d ",old[stateIndex].boardState[i]);
	//printf("%s\n","");
	//if(IsGoal(stateIndex))
	//{
	//			printf("%s\n","found goal");
	//	for(int i=0;i<SIZE;i++)
	//		printf("%d ",old[stateIndex].boardState[i]);
	//	printf("%s\n","");
	//	goalDepth=old[stateIndex].g;
	//	return 100;
	//}

	//printf("%s\n","generating children");
	// Generate all the immediate children:
	newg=g+1;
	for (int newMove = 0; newMove < SIZE; newMove++)
	{
		if (!OperMat[PrevMove][newMove])// 0 -> 4 -> 8
		 {
			 //printf("%s %d\n","not allowed move: ",opindex);
			continue;
		}


		//newblank=opindex;
		MakeMove(stateIndex,newMove);
		if(IsGoal(stateIndex))
		{
			if(UpperLimit>newg) UpperLimit=newg;
			printf("%s %d\n","Found Goal:::",UpperLimit);
			return 0;
		}
		//printf("%s","the child node is:");
		//for (int l=0;l<SIZE;l++)
		//	printf("%d ",old[stateIndex].boardState[l]);
		//printf("%s\n","");
		//ConvertStateToDual(stateIndex);
		newh=GetHuristicRegular(stateIndex,0);
		newh=MAX(h-1,newh);
		minf=INFINITY;
		//printf("%s\n","beforeLH");
		
		if(newh+newg<=-1 )//&& newh+newg>NextBestF)
		{
			delta=0;
			minf=INFINITY;
			//printf("%s %d %s %d %s %d %s %d\n","delta=",delta,"h=",newh,"g=",newg,"lookahead=",lookahead);
			int tempH=0;//HBLookahead3(state,newg,newh,lookahead,newMove);
			//printf("%s %d %s %d\n","delta=",delta,"h=",h);
			
			//printf("%s %d %s %d %s %d %s %d %s %d\n","delta=",delta,"h=",newh,"g=",newg,"tempH=",tempH,"lookahead=",lookahead);
			//string mystr;
			//getline (cin,mystr);
			newh=MAX(newh,tempH);
			//if(minf<=newh) 
			//{
			//	printf("%s %d %s %d\n","minf equals to newh after LH, minf=",minf,"newh=",newh);
			//	string mystr;
			//	getline (cin,mystr);
			//}
		}
		else
			minf=MAX(newh+newg,h+g);
		//printf("%s\n","afterLH");
		//printf("%s","the child node is:");
		//for (int l=0;l<SIZE;l++)
		//	printf("%d ",old[stateIndex].boardState[l]);
		//printf("%s\n","");
		//printf("%s %d %s %d\n","newh=",newh,"minf=",minf);
		//string mystr;
		//getline (cin,mystr);
		//printf("%s %d\n","child h=",newh);
		maxH=MAX(maxH,newh-2);

		 newf=newh+newg;
		// if(minf<UpperLimit)
		// {
		 //Add the child to the children list
		 for(int i=0;i<SIZE;i++)
			children[ChildNum].boardState[i]=old[stateIndex].boardState[i];
		 children[ChildNum].add2Open=false;
		 children[ChildNum].g=newg;
		 children[ChildNum].h=newh;
		 children[ChildNum].PrevMove=newMove;
		 children[ChildNum].cost=newh+newg;
	//	 printf("%s %d %s %d\n","childf=",children[ChildNum].g+children[ChildNum].h,"childc=",children[ChildNum].cost);
	//	    string mystr;
	//getline (cin,mystr);
		 if(CostArr[children[ChildNum].cost]==-1) CostArr[children[ChildNum].cost]=1;
		 generated++;
		 ChildNum++;
		
		// }
		 MakeMove(stateIndex,newMove);
		// printf("%s","state after undo:");
		//for (int l=0;l<SIZE;l++)
		//	printf("%d ",old[stateIndex].boardState[l]);
		//printf("%s\n","");
	}
	//string mystr;
	//getline (cin,mystr);


	//printf("%s %d\n","maxh=",maxH);
	//Now, update the children heuristic based on maxH found:
	for (int i=0;i<ChildNum;i++)
	{
		//printf("%s %d\n","child h before change:",children[i].h);
		children[i].h=MAX(maxH,children[i].h);
		///printf("%s %d\n","child h after change1:",children[i].h);
		//if(children[i].g+children[i].h<old[stateIndex].g+old[stateIndex].h)
		//	children[i].h=old[stateIndex].h-1;
		//printf("%s %d\n","child h after change2:",children[i].h);

		//Search for the child in memory
		hashval=CalcHash(children[i].boardState);
		newindex=SearchHash(children[i].boardState,hashval);
		if(newindex==stateIndex) newindex=-1;
		//if(newindex!=-1 && old[newindex].PrevMove!=children[i].PrevMove)
		//{
		//	printf("%s\n","different prev moves");
		//string mystr;
		//getline (cin,mystr);
		//}
		//printf("%s %d\n","newindex=",newindex);

		bool boo=true;
		// if the state already exists
		if(newindex!=-1)
		{
			
			//Check if exists in close list
			if(old[newindex].heaplink==-1)
			{
				//printf("%s","Found the state in close ");
				//for(int j=0;j<SIZE;j++)
				//	printf("%d ",old[newindex].boardState[j]);
				//printf("%s %d %s %d\n","h=",old[newindex].h," g=",old[newindex].g);
				//printf("%s %d %s %d\n","childh=",children[i].h," chilg=",children[i].g);
				//string mystr;
				//getline (cin,mystr);
				//FoundInC++;
				//if(old[newindex].h>children[i].h)
				//{
				//	children[i].h=old[newindex].h;
				//	UpdateH=true;
				//}
				if(old[newindex].g<=children[i].g)
				{
					boo=false;
					//if(old[newindex].h>=children[i].h)
					//boo=false;

				}
				//else
				//if(old[newindex].g==children[i].g && old[newindex].h>=children[i].h)
				//		boo=false;
				//if(boo) //(g in close is lower than g in children)
				else
				{
					reopened++;
					FoundInC++;
						boo=true;
						for (int j=0;j<SIZE;j++)
						old[newindex].boardState[j]=-1;
					old[newindex].h=-1;
					old[newindex].g=-1;
				}
				
			}// end if - if in close list
		
			//else //the node is in the open list
			if(old[newindex].heaplink!=-1)
			{
				//printf("%s","Found the state in close ");
				//for(int j=0;j<SIZE;j++)
				//	printf("%d ",old[newindex].boardState[j]);
				//printf("%s %d %s %d\n","h=",old[newindex].h," g=",old[newindex].g);
				//printf("%s %d %s %d\n","childh=",children[i].h," chilg=",children[i].g);
				//string mystr;
				//getline (cin,mystr);
				boo=false;
				//FoundInO++;

				//if(old[newindex].h>children[i].h)
				//	children[i].h=old[newindex].h;
				if(old[newindex].g>children[i].g)
				{
					reopened++;
					FoundInO++;
					//old[newindex].g=children[i].g;
					boo=false;
					if(old[newindex].h<children[i].h)
						old[newindex].h=children[i].h;
					if(old[newindex].cost!=children[i].cost) old[newindex].cost=MAX(children[i].cost,old[newindex].cost);
					ReOpen(newindex,children[i].g,children[i].PrevMove);
				}

				//---*********** this part worked ********************---
				//if(old[newindex].g>children[i].g)
				//{
				//	old[newindex].g=children[i].g;
				//	boo=false;
				//	if(old[newindex].h<children[i].h)
				//		old[newindex].h=children[i].h;
				//	ReOpen(newindex,old[newindex].g,children[i].PrevMove);
				//}
				//else //(g in close is lower than g in children)
				//{
				//	if(old[newindex].g==children[i].g)
				//	{
				//	if(old[newindex].h<children[i].h)
				//	{
				//		boo=false;
				//		old[newindex].h=children[i].h;
				//		ReOpen(newindex,old[newindex].g,children[i].PrevMove);
				//	}
				//	}
				//}//---*********** this part worked ********************---
			}
}//end if (for existing child)
		else
			boo=true;
		//boo=true; //for testing
		if (boo) 
		{
			//printf("%s\n","adding the child");
			children[i].add2Open=true;
		}
		else
		{
			//printf("%s\n","NOT adding the child");
			children[i].add2Open=false;
		}

		
	//string mystr;
	//getline (cin,mystr);
	}//end for

	//After updating the children heuristic, need to find new maxH
	int maxLH=0;
	for (int i=0;i<ChildNum;i++)
	{
		if(children[i].add2Open==true )//&& children[i].h+children[i].g>NextBestF )
		{
			if(children[i].h+children[i].g<=lookahead && children[i].h+children[i].g>NextBestF)
			{
				delta=0;
				minf=INFINITY;
				printf("%s %d %s %d %s %d %s %d\n","delta=",delta,"h=",children[i].h,"g=",children[i].g,"lookahead=",lookahead);
				int tempH=oHBLookahead3(children[i].boardState,children[i].g,children[i].h,lookahead,children[i].PrevMove);
				printf("%s %d %s %d\n","delta=",delta,"h=",tempH);
			
				//printf("%s %d %s %d %s %d %s %d %s %d\n","delta=",delta,"h=",newh,"g=",newg,"tempH=",tempH,"lookahead=",lookahead);
				//string mystr;
				//getline (cin,mystr);
				children[i].h=MAX(children[i].h,tempH-2);
				//if(minf<=newh) 
				//{
				//	printf("%s %d %s %d\n","minf equals to newh after LH, minf=",minf,"newh=",newh);
				//	string mystr;
				//	getline (cin,mystr);
				//}
			}
			else
				minf=children[i].h+children[i].g;
			children[i].cost=MAX(minf,children[i].cost);
		//printf("%s\n","afterLH");
		//printf("%s","the child node is:");
		//for (int l=0;l<SIZE;l++)
		//	printf("%d ",old[stateIndex].boardState[l]);
		//printf("%s\n","");
		//printf("%s %d %s %d\n","newh=",newh,"minf=",minf);
		//string mystr;
		//getline (cin,mystr);
		//printf("%s %d\n","child h=",newh);
		maxLH=MAX(maxLH,children[i].h-2);

		}
	}//end for

	//printf("%s\n","-- before insert to open --");
	// Now we can add the children to the OPEN list
	for (int i=0;i<ChildNum;i++)
	{
		if(children[i].add2Open)
		{
			children[i].h=MAX(maxLH,children[i].h);
			if(children[i].g+children[i].h>children[i].cost) children[i].cost= children[i].g+children[i].h;
			if(children[i].h+children[i].g<UpperLimit)
			{
			//printf("%s %d\n","childh before change:",children[i].h);
			//children[i].h=MAX(maxH,children[i].h);
			//printf("%s %d\n","childh after change:",children[i].h);
				hashval=CalcHash(children[i].boardState);
				if(children[i].h+children[i].g<=NextBestF)
				{
					IE++;
					int cindex=Add2Close(children[i].boardState,hashval,children[i].PrevMove,children[i].g,children[i].h);//,children[i].cost);
					//printf("%s %d %s %d\n","Perform IE-->NextBestF=",NextBestF,"f=",children[i].g+children[i].h);
					int r=oIIBExpandNodeLH(cindex,children[i].g,children[i].h,children[i].PrevMove,lookahead);
					if (r==0) return 0;
				}
				else
				{
					//printf("%s %d %s %d\n","Adding, f=",children[i].g+children[i].h,"cost=",children[i].cost);
					
					InsertHash2(children[i].boardState,hashval,children[i].PrevMove,children[i].g,children[i].h);//,children[i].cost);
				}
			}

		}
	}//end for
	old[stateIndex].h=MAX(old[stateIndex].h,maxH-1);

return -1;

}

int HBLookahead3(short state[SIZE],int g, int h, int lookahead, int PrevMove)
{
	int opindex;
	int newblank;
	int newg;
	int newh;
	int rh;
	int maxH;



	rh=0;


	//printf("%s","Parent array:");
	//for (int i=0;i<SIZE;i++)
	//	printf("%d ",old[stateIndex].boardState[i]);
	//printf("%s\n","");
	//if the cost is lower than lookahead and the state is not goal - need to develope its children
	newg=g+1; // calculate child g
	for (int newMove = 0; newMove < SIZE; newMove++)
	{
		if (!OperMat[PrevMove][newMove])// 0 -> 4 -> 8
		 {
			 //printf("%s %d\n","not allowed move: ",opindex);
			continue;
		}

		//printf("%s","parent: ");
		//for (int i=0;i<SIZE;i++)
		//	 printf("%d ",state[i]);
		//printf("%s\n","");
		MakeMove(state,newMove); //generate a child
		//printf("%s","Goining deeper: ");
		//for (int i=0;i<SIZE;i++)
		//	 printf("%d ",state[i]);
		//printf("%s\n","");
		//if(IsGoal(stateIndex)) printf("%s %d\n","goal depht is-->>", newg);

		 ImmediateGenerated++;

		// ConvertStateToDual(state);
		 newh=GetHuristicRegular(state,0); //calculate child h
		 if(/*newh+newg<=lookahead &&*/ newh==0 && IsGoal(state))
		 {
			 if(newg<UpperLimit) UpperLimit=newg;
			 printf("%s %d\n","Found Goal==>>",UpperLimit);
			 MakeMove(state,newMove);
			 continue;
		 }
		 
		 	if(newh+newg<minf && newh+newg>lookahead)
			 {
				// printf("%s %d %s %d\n","Updating minf:",minf,"new value:",newg+newh);
				 minf=newh+newg;
			 }
		 //printf("%s %d %s %d %s %d\n","newh=",newh,"newg=",newg,"lookahead=",lookahead);
		 //string mystr;
		//getline (cin,mystr);

		
		 if( newg+newh<=lookahead && newg+newh<UpperLimit) // if the child cost is lower than the current goal - perform DFS
		 {
			// IGSameV++;
			 //rh=HBLookahead3(stateIndex,newg,newh,lookahead,newMove);
			 newh=HBLookahead3(state,newg,newh,lookahead,newMove);
			 //printf("%s %d\n","getting h:",newh);
		 }
		// printf("%s %d\n","after newh=",newh);
		 
		// else
		// {
		  //printf("%s %d\n","h before change:",h);
		// if(newh-1>h)
			// printf("%s %d %s %d %s %d %s %d\n","-->>newh=",newh,"newg=",newg,"h=",h,"g=",g);
			 h=MAX(h,newh-1);
			 //	printf("%s","child to change array:");
				//for (int i=0;i<SIZE;i++)
				//	printf("%d ",old[stateIndex].boardState[i]);
				//printf("%s\n","");
			 MakeMove(state,newMove);
			// printf("%s","Changed to-->> array:");
			//for (int i=0;i<SIZE;i++)
			//	printf("%d ",old[stateIndex].boardState[i]);
			//printf("%s\n","");
			//string mystr;
			//getline (cin,mystr);
			
			 //h=MAX(h,rh-1);
			// printf("%s %d\n","h after change:",h);
			// string mystr;
			// getline (cin,mystr);
			 if(h+g<minf && h+g>lookahead)
			 {
				// printf("%s %d %s %d\n","Updating minf:",minf,"new value:",newg+newh);
				 minf=h+g;
			 }
			 if(g+h>lookahead)
			 {
				// printf("%s %d %s %d\n","sending h:",h,"g:",g);
				 return h;
			 }
		// }
		//MakeMove(stateIndex,newMove);
		 

		 //printf("%s %d\n","h before update:",h);

		 	 
		 		 
	}//end for
	//printf("%s %d %s %d\n","at the end sending h:",h,"g:",g);
return h;
}//End BLookahead

int HBLookahead3(int stateIndex,int g, int h, int lookahead, int PrevMove)
{
	int opindex;
	int newblank;
	int newg;
	int newh;
	int rh;
	int maxH;



	rh=0;


	//printf("%s","Parent array:");
	//for (int i=0;i<SIZE;i++)
	//	printf("%d ",old[stateIndex].boardState[i]);
	//printf("%s\n","");
	//if the cost is lower than lookahead and the state is not goal - need to develope its children
	newg=g+1; // calculate child g
	for (int newMove = 0; newMove < SIZE; newMove++)
	{
		if (!OperMat[PrevMove][newMove])// 0 -> 4 -> 8
		 {
			 //printf("%s %d\n","not allowed move: ",opindex);
			continue;
		}

		MakeMove(stateIndex,newMove); //generate a child
		//printf("%s","Goining deeper: ");
		//for (int i=0;i<SIZE;i++)
		//	 printf("%d ",old[stateIndex].boardState[i]);
		//printf("%s\n","");
		//if(IsGoal(stateIndex)) printf("%s %d\n","goal depht is-->>", newg);

		 ImmediateGenerated++;

		 //ConvertStateToDual(stateIndex);
		 newh=GetHuristicRegular(stateIndex,0); //calculate child h
		 if(newh+newg<=lookahead && newh==0 && IsGoal(stateIndex))
		 {
			 if(newg<UpperLimit) UpperLimit=newg;
			 printf("%s %d\n","Found Goal==>>",UpperLimit);
			 		
		 	//string mystr;
			//getline (cin,mystr);
			// printf("%s %d %s %d\n","NextbestF=",NextBestF,"pf=",old[stateIndex].h+old[stateIndex].g);
			 MakeMove(stateIndex,newMove);
			 continue;
		 }
		 	if(newh+newg<minf && newh+newg>lookahead)
			 {
				// printf("%s %d %s %d\n","Updating minf:",minf,"new value:",newg+newh);
				 minf=newh+newg;
			 }
		 
		// printf("%s %d %s %d %s %d\n","newh=",newh,"newg=",newg,"lookahead=",lookahead);
		 //string mystr;
		//	getline (cin,mystr);
		 if( newg+newh<=lookahead && newg+newh<UpperLimit) // if the child cost is lower than the current goal - perform DFS
		 {
			// IGSameV++;
			 //rh=HBLookahead3(stateIndex,newg,newh,lookahead,newMove);
			 newh=HBLookahead3(stateIndex,newg,newh,lookahead,newMove);
			// printf("%s %d\n","getting h:",newh);
		 }
		// printf("%s %d\n","after newh=",newh);
		 
		// else
		// {
		 // printf("%s %d\n","h before change:",h);
			 h=MAX(h,newh-1);
		//printf("%s %d\n","h after change:",h);
			 //	printf("%s","child to change array:");
				//for (int i=0;i<SIZE;i++)
				//	printf("%d ",old[stateIndex].boardState[i]);
				//printf("%s\n","");
			 MakeMove(stateIndex,newMove);
			// printf("%s","Changed to-->> array:");
			//for (int i=0;i<SIZE;i++)
			//	printf("%d ",old[stateIndex].boardState[i]);
			//printf("%s\n","");
			//string mystr;
			//getline (cin,mystr);
			
			 //h=MAX(h,rh-1);
			// printf("%s %d\n","h after change:",h);
			// string mystr;
			// getline (cin,mystr);
			 if(h+g<minf && h+g>lookahead)
			 {
				// printf("%s %d %s %d\n","Updating minf:",minf,"new value:",newg+newh);
				 minf=h+g;
			 }
			 if(g+h>lookahead)
			 {
				//printf("%s %d %s %d\n","sending h:",h,"g:",g);
				 return h;
			 }
		// }
		//MakeMove(stateIndex,newMove);
		 

		 //printf("%s %d\n","h before update:",h);

		 	 
		 		 
	}//end for
 if(h+g<minf && h+g>lookahead)
			 {
				// printf("%s %d %s %d\n","Updating minf:",minf,"new value:",newg+newh);
				 minf=h+g;
			 }
return h;
}//End BLookahead
int IIBExpandNodeLH(int stateIndex,int g,int h, int PrevMove,int lookahead)
{
	 struct child
	 {                           
		 short boardState[SIZE];
		 //int boardState[SIZE];
		 short g;                                      /* distance from initial state */
		 short h;                        /* static heuristic distance from goal state */
		 int cost;
		 short PrevMove;                                /* previous position of blank */
		 bool add2Open;
		 int newindex;
	 } children[SIZE];

	int blank;
	int newblank;
	int newindex;
	int opindex;

	int newg;
	int newh;
	int newf;
	int tile;
	int flag=-1;

	int hashval;
	int maxH;  //holds the maximum H between all immediate children
	int ChildNum;

	FILE *solution;

	//maxH=0;
	maxH=h-1;
	ChildNum=0;

	//printf(" %s %d \n","**************** IG=",ImmediateGenerated);
	// First check if the state is the goal
	//printf("%s","checking for goal:");
	//for (int i=0;i<SIZE;i++)
	//	printf("%d ",old[stateIndex].boardState[i]);
	//printf("%s\n","");
	//if(IsGoal(stateIndex))
	//{
	//			printf("%s\n","found goal");
	//	for(int i=0;i<SIZE;i++)
	//		printf("%d ",old[stateIndex].boardState[i]);
	//	printf("%s\n","");
	//	goalDepth=old[stateIndex].g;
	//	return 100;
	//}

	//printf("%s\n","generating children");
	// Generate all the immediate children:
	newg=g+1;
	for (int newMove = 0; newMove < SIZE; newMove++)
	{
		if (!OperMat[PrevMove][newMove])
		 {
			 //printf("%s %d\n","not allowed move: ",opindex);
			continue;
		}

		//newblank=opindex;
		MakeMove(stateIndex,newMove);
		if(IsGoal(stateIndex))
		{
			if(UpperLimit>newg) UpperLimit=newg;
			printf("%s %d\n","Found Goal:::",UpperLimit);
			//return 0;
		}
		//printf("%s","the child node is:");
		//for (int l=0;l<SIZE;l++)
		//	printf("%d ",old[stateIndex].boardState[l]);
		//printf("%s\n","");
		//ConvertStateToDual(stateIndex);
		newh=GetHuristicRegular(stateIndex,0);
		//printf("%s %d ","bnewh:",newh);
		//if(maxH>newh) BUpdate++;
		newh=MAX(maxH,newh);
	//	printf("%s %d %s %d\n","anewh:",newh,"maxH=",maxH);
		minf=INFINITY;
		//printf("%s\n","beforeLH");
		
			
		//printf("%s\n","afterLH");
		//printf("%s","the child node is:");
		//for (int l=0;l<SIZE;l++)
		//	printf("%d ",old[stateIndex].boardState[l]);
		//printf("%s\n","");
		//printf("%s %d %s %d %s %d\n","newh=",newh,"newg=",newg,"minf=",minf);
		//string mystr;
		//getline (cin,mystr);
		//printf("%s %d\n","child h=",newh);
		maxH=MAX(maxH,newh-2);

		 newf=newh+newg;
		 if(newf<UpperLimit)
		 {
		  hashval=CalcHash(children[ChildNum].boardState);
		  children[ChildNum].newindex=SearchHash(children[ChildNum].boardState,hashval);
		  if(children[ChildNum].newindex==stateIndex) children[ChildNum].newindex=-1;
		  if( children[ChildNum].newindex!=-1 && old[children[ChildNum].newindex].g<=children[ChildNum].g) children[ChildNum].newindex=MAX+1;
		  if(children[ChildNum].newindex<MAX+1)
		  {
		 //Add the child to the children list
		 for(int i=0;i<SIZE;i++)
			children[ChildNum].boardState[i]=old[stateIndex].boardState[i];
		 children[ChildNum].add2Open=false;
		 children[ChildNum].g=newg;
		 children[ChildNum].h=newh;
		 children[ChildNum].PrevMove=newMove;
		 children[ChildNum].cost=MAX(newf,bestc);//newf;
		  }
		  else
		  {
			children[ChildNum].newindex=-100;
		  }
	//	 printf("%s %d %s %d\n","childf=",children[ChildNum].g+children[ChildNum].h,"childc=",children[ChildNum].cost);
	//	    string mystr;
	//getline (cin,mystr);
		 
		 generated++;
		 ChildNum++;
		
		 }
		 MakeMove(stateIndex,newMove);
		// printf("%s","state after undo:");
		//for (int l=0;l<SIZE;l++)
		//	printf("%d ",old[stateIndex].boardState[l]);
		//printf("%s\n","");
	}
	//string mystr;
	//getline (cin,mystr);


	//printf("%s %d\n","maxh=",maxH);
	//Now, update the children heuristic based on maxH found:
	for (int i=0;i<ChildNum;i++)
	{

		children[i].h=MAX(maxH,children[i].h); 
	}

	int maxLH=0;
	for (int i=0;i<ChildNum;i++)
	{
		//for(int j=0;j<SIZE;j++)
		//	printf("%d ",children[i].boardState[j]);
		//printf("%s %d %s %d %s %d\n","h:",children[i].h,"g:",children[i].g,"lookahead:",lookahead);
		//printf("%s %d\n","---In lookahead loop----",lookahead);
		//printf("%s %d %s %d %s %d\n","Before LH--childh=",children[i].h,"maxH=",maxH,"maxLH=",maxLH);
		//update according to the siblings (brothers) - do we need it?
		//if(maxLH>children[i].h) LHUpdate++;
		children[i].h=MAX(maxLH,children[i].h);
		int flag=0;
		//if(children[i].h+children[i].g<=old[stateIndex].h+old[stateIndex].g) //&& lookahead<old[stateIndex].cost)
		//	flag=1;
		flag=0;
		//printf("%s %d %s %d %s %d %s %d\n","lookahead=",lookahead,"h=",children[i].h,"g=",children[i].g,"NextBestF=",NextBestF);
		if(children[i].h+children[i].g<=lookahead && flag==0 && children[i].h+children[i].g<UpperLimit)
		{
			//LHFrom++;
			//LHnodes++;
			minf=INFINITY;
			//printf("%s %d %s %d %s %d %s %d\n","delta=",delta,"h=",newh,"g=",newg,"lookahead=",lookahead);
			int tempH=0;
			int tempLH=children[i].h+children[i].g;
			/*printf("%s %d %s %d %s %d %s %d\n","g=",children[i].g,"h=",children[i].h,"minf=",minf,"NextBestF=",NextBestF);*/
			//int tempLH=lookahead;
			while(tempLH<=lookahead && tempLH<UpperLimit)
			{
				minf=INFINITY;
				tempH=HBLookahead3(children[i].boardState,children[i].g,children[i].h,tempLH,children[i].PrevMove);
				tempLH=MAX(tempLH+1,tempH+children[i].g);
			}
			
			if(tempH>children[i].h)
			{
			//	LHUpdate++;
			//	printf("%s %d %s %d\n","tempH:",tempH,"children[i].h=",children[i].h);
			//	string mystr;
			//	getline (cin,mystr);
			}
			children[i].h=MAX(children[i].h,tempH);
			children[i].cost=MAX(minf,children[i].cost);
			if(maxLH<children[i].h-2)
			{
				//printf("%s %d %s %d\n","maxLH:",maxLH,"children[i].h-2=",children[i].h-2);
				//string mystr;
				//getline (cin,mystr);
			}
			maxLH=MAX(maxLH,children[i].h-2);
			//printf("%s %d %s %d %s %d %s %d\n","g=",children[i].g,"h=",children[i].h,"minf=",minf,"NextBestF=",NextBestF);
			//printf("%s %d\n","maxLH:",maxLH);
			//printf(" %s %d \n","***********  IG=",ImmediateGenerated);
		}
		
	}
		//printf("%s %d %s %d %s %d %s %d\n","After LH--childh=",children[i].h,"maxH=",maxH,"maxLH=",maxLH,"IG=",ImmediateGenerated);
	//printf(" %s %d \n","***********  IG=",ImmediateGenerated);
	//	string mystr;
	//	getline (cin,mystr);
		//children[i].h=MAX(maxH,children[i].h);
	for (int i=0;i<ChildNum;i++)
	{
		//if(maxLH>children[i].h) BLHUpdate++;
		children[i].h=MAX(children[i].h,maxLH);
		if(children[i].cost<children[i].h+children[i].g) children[i].cost=children[i].h+children[i].g;
		///printf("%s %d\n","child h after change1:",children[i].h);
		//if(children[i].g+children[i].h<old[stateIndex].g+old[stateIndex].h)
		//	children[i].h=old[stateIndex].h-1;
		//printf("%s %d\n","child h after change2:",children[i].h);

		//Search for the child in memory
		//hashval=CalcHash(children[i].boardState);
		//newindex=SearchHash(children[i].boardState,hashval);
		//if(newindex==stateIndex) newindex=-1;

		//if(newindex!=-1 && old[newindex].PrevMove!=children[i].PrevMove)
		//{
		//	printf("%s\n","different prev moves");
		//string mystr;
		//getline (cin,mystr);
		//}
		//printf("%s %d\n","newindex=",newindex);

		bool boo=true;
		// if the state already exists
		int newindex=children[i].newindex;
		if(children[i].newindex!=-1)
		{
			
			//Check if exists in close list
			if(old[newindex].heaplink==-1)
			{
				//printf("%s","Found the state in close ");

				if(old[newindex].g<=children[i].g)
				{
					boo=false;
					//if(old[newindex].h>=children[i].h)
					//boo=false;

				}
				//else
				//if(old[newindex].g==children[i].g && old[newindex].h>=children[i].h)
				//		boo=false;
				//if(boo) //(g in close is lower than g in children)
				else
				{
					reopened++;
					FoundInC++;
						boo=true;
						for (int j=0;j<SIZE;j++)
						old[newindex].boardState[j]=-1;
					old[newindex].h=-1;
					old[newindex].g=-1;
				}
				
			}// end if - if in close list
		
			//else //the node is in the open list
			if(old[newindex].heaplink!=-1)
			{
				//printf("%s","Found the state in close ");
				//for(int j=0;j<SIZE;j++)
				//	printf("%d ",old[newindex].boardState[j]);
				//printf("%s %d %s %d\n","h=",old[newindex].h," g=",old[newindex].g);
				//printf("%s %d %s %d\n","childh=",children[i].h," chilg=",children[i].g);
				//string mystr;
				//getline (cin,mystr);
				boo=false;
				//FoundInO++;

				//if(old[newindex].h>children[i].h)
				//	children[i].h=old[newindex].h;
				if(old[newindex].g>children[i].g)
				{
					reopened++;
					FoundInO++;
					//old[newindex].g=children[i].g;
					boo=false;
					if(old[newindex].h<children[i].h)
						old[newindex].h=children[i].h;
					//if(old[newindex].cost!=children[i].cost) old[newindex].cost=children[i].cost;
					FReOpen(newindex,children[i].g,children[i].PrevMove);
				}

				//---*********** this part worked ********************---
				//if(old[newindex].g>children[i].g)
				//{
				//	old[newindex].g=children[i].g;
				//	boo=false;
				//	if(old[newindex].h<children[i].h)
				//		old[newindex].h=children[i].h;
				//	ReOpen(newindex,old[newindex].g,children[i].PrevMove);
				//}
				//else //(g in close is lower than g in children)
				//{
				//	if(old[newindex].g==children[i].g)
				//	{
				//	if(old[newindex].h<children[i].h)
				//	{
				//		boo=false;
				//		old[newindex].h=children[i].h;
				//		ReOpen(newindex,old[newindex].g,children[i].PrevMove);
				//	}
				//	}
				//}//---*********** this part worked ********************---
			}
}//end if (for existing child)
		else
			boo=true;
		//boo=true; //for testing
		if (boo) 
		{
			//printf("%s\n","adding the child");
			children[i].add2Open=true;
		}
		else
		{

		// falseLH++;
			//printf("%s\n","NOT adding the child");
			children[i].add2Open=false;
		}

		
	//string mystr;
	//getline (cin,mystr);
	}//end for

	//After updating the children heuristic, need to find new maxH
	//int maxLH=0;
	//for (int i=0;i<ChildNum;i++)
	//{
	//	//if(children[i].add2Open==true )//&& children[i].h+children[i].g>NextBestF )
	//	//{
	//	children[i].h=MAX(maxLH,children[i].h);
	//		if(children[i].h+children[i].g<=lookahead && children[i].h+children[i].g>NextBestF)
	//		{
	//			delta=0;
	//			minf=INFINITY;
	//			//printf("%s %d %s %d %s %d %s %d\n","delta=",delta,"h=",newh,"g=",newg,"lookahead=",lookahead);
	//			int tempH=HBLookahead3(children[i].boardState,children[i].g,children[i].h,lookahead,children[i].PrevMove);
	//			//printf("%s %d %s %d\n","delta=",delta,"h=",h);
	//		
	//			//printf("%s %d %s %d %s %d %s %d %s %d\n","delta=",delta,"h=",newh,"g=",newg,"tempH=",tempH,"lookahead=",lookahead);
	//			//string mystr;
	//			//getline (cin,mystr);
	//			children[i].h=MAX(children[i].h,tempH-2);
	//			//if(minf<=newh) 
	//			//{
	//			//	printf("%s %d %s %d\n","minf equals to newh after LH, minf=",minf,"newh=",newh);
	//			//	string mystr;
	//			//	getline (cin,mystr);
	//			//}
	//		}
	//		else
	//			minf=children[i].h+children[i].g;
	//		children[i].cost=MAX(minf,children[i].cost);
	//	//printf("%s\n","afterLH");
	//	//printf("%s","the child node is:");
	//	//for (int l=0;l<SIZE;l++)
	//	//	printf("%d ",old[stateIndex].boardState[l]);
	//	//printf("%s\n","");
	//	//printf("%s %d %s %d\n","newh=",newh,"minf=",minf);
	//	//string mystr;
	//	//getline (cin,mystr);
	//	//printf("%s %d\n","child h=",newh);
	//	maxLH=MAX(maxLH,children[i].h-2);

	//	//}
	//}//end for

	//printf("%s\n","-- before insert to open --");
	// Now we can add the children to the OPEN list
	for (int i=0;i<ChildNum;i++)
	{
		if(children[i].add2Open)
		{
			children[i].h=MAX(maxLH,children[i].h);
			if(children[i].g+children[i].h>children[i].cost) children[i].cost= children[i].g+children[i].h;
			if(children[i].h+children[i].g<UpperLimit)
			{
			//printf("%s %d\n","childh before change:",children[i].h);
			//children[i].h=MAX(maxH,children[i].h);
			//printf("%s %d\n","childh after change:",children[i].h);
				hashval=CalcHash(children[i].boardState);
				//if(children[i].h+children[i].g<=NextBestF)
				//{
				//	IE++;
				//	if(CostArr[children[i].cost]==-1) CostArr[children[i].cost]=1;
				//	int cindex=FAdd2Close(children[i].boardState,hashval,children[i].PrevMove,children[i].g,children[i].h,children[i].cost);
				//////	//printf("%s %d %s %d\n","Perform IE-->NextBestF=",NextBestF,"f=",children[i].g+children[i].h);
				//	int r=IIBExpandNodeLH(cindex,children[i].g,children[i].h,children[i].PrevMove,lookahead);
				//////	//if (r==0) return 0;
				//}
				//else
				//{
					//printf("%s %d %s %d\n","Adding, f=",children[i].g+children[i].h,"cost=",children[i].cost);
					if(CostArr[children[i].cost]==-1) CostArr[children[i].cost]=1;
					FInsertHash2(children[i].boardState,hashval,children[i].PrevMove,children[i].g,children[i].h,children[i].cost);
				//}
			}

		}
	}//end for
	old[stateIndex].h=MAX(old[stateIndex].h,maxH-1);

return -1;

}
int IIBExpandNodeLH2(int stateIndex,int g,int h, int PrevMove,int lookahead)
{
	 struct child
	 {                           
		 short boardState[SIZE];
		 //int boardState[SIZE];
		 short g;                                      /* distance from initial state */
		 short h;                        /* static heuristic distance from goal state */
		 int cost;
		 short PrevMove;                                /* previous position of blank */
		 bool add2Open;
	 } children[SIZE];

	int blank;
	int newblank;
	int newindex;
	int opindex;

	int newg;
	int newh;
	int newf;
	int tile;
	//int flag=-1;

	int hashval;
	int maxH;  //holds the maximum H between all immediate children
	int ChildNum;

	FILE *solution;

	//maxH=0;
	maxH=h-1;
	ChildNum=0;

	//printf(" %s %d \n","***********  IG=",ImmediateGenerated);
	// First check if the state is the goal
	//printf("%s","checking for goal:");
	//for (int i=0;i<SIZE;i++)
	//	printf("%d ",old[stateIndex].boardState[i]);
	//printf("%s\n","");
	//if(IsGoal(stateIndex))
	//{
	//			printf("%s\n","found goal");
	//	for(int i=0;i<SIZE;i++)
	//		printf("%d ",old[stateIndex].boardState[i]);
	//	printf("%s\n","");
	//	goalDepth=old[stateIndex].g;
	//	return 100;
	//}

	//printf("%s\n","generating children");
	// Generate all the immediate children:
	newg=g+1;
	for (int newMove = 0; newMove < SIZE; newMove++)
	{
		if (!OperMat[PrevMove][newMove])
		 {
			 //printf("%s %d\n","not allowed move: ",opindex);
			continue;
		}

		//newblank=opindex;
		MakeMove(stateIndex,newMove);
		if(IsGoal(stateIndex))
		{
			if(UpperLimit>newg) UpperLimit=newg;
			printf("%s %d\n","Found Goal:::",UpperLimit);
			return 0;
		}
		//printf("%s","the current node is:");
		//for (int l=0;l<SIZE;l++)
		//	printf("%d ",old[stateIndex].boardState[l]);
		//printf("%s\n","");
		//ConvertStateToDual(stateIndex);
		
		newh=GetHuristicRegular(stateIndex,0);
		//printf("%s %d %s %d\n","bnewh :",newh,"maxH=",maxH);
		if(maxH>newh) BUpdate++;
		int flag=0;
		//if(newh+newg<=old[stateIndex].h+old[stateIndex].g) flag=1;
		newh=MAX(maxH,newh);
		minf=INFINITY;
		
		
		//printf("%s\n","beforeLH");
		//printf("%s %d %s %d %s %d %s %d\n","newh before change:",newh,"newg=",newg,"NextbestF=",NextBestF,"lookahead=",lookahead);
		if(newh+newg<=lookahead && flag==0 && newh+newg<UpperLimit)
		{
			LHnodes++;
			//printf("%s\n","-----In lookahead loop--------");
			//for(int i=0;i<SIZE;i++)
			//	printf("%d ",old[stateIndex].boardState[i]);
			//printf("%s\n","");
			
			
			//int tempLH=newh+newg;
			int tempLH=lookahead;
			int tempH=0;
			//printf("%s %d %s %d %s %d %s %d\n","delta=",delta,"h=",newh,"g=",newg,"lookahead=",lookahead);
			//while(tempLH<=lookahead && tempLH<UpperLimit)
			//{
				
				minf=INFINITY;
				tempH=HBLookahead3(stateIndex,newg,newh,tempLH,newMove);
				//printf("%s %d %s %d\n","minf=",minf,"lookahead=",lookahead);
				tempLH=minf;
			//}
			//printf("%s %d\n","tempH=",tempH,"h=",h);
			
			//printf("%s %d %s %d %s %d %s %d %s %d\n","delta=",delta,"h=",newh,"g=",newg,"tempH=",tempH,"lookahead=",lookahead);
			//string mystr;
			//getline (cin,mystr);
			if(tempH>newh) LHUpdate++;
			newh=MAX(newh,tempH);
			//printf(" %s %d \n","***********  IG=",ImmediateGenerated);
			//if(minf<=newh) 
			//{
			//	printf("%s %d %s %d\n","minf equals to newh after LH, minf=",minf,"newh=",newh);
			//	string mystr;
			//	getline (cin,mystr);
			//}
		}
		else
			minf=newg+newh;//,old[stateIndex].cost);
		//printf("%s\n","afterLH");
		//printf("%s","the child node is:");
		//for (int l=0;l<SIZE;l++)
		//	printf("%d ",old[stateIndex].boardState[l]);
		//printf("%s\n","");
		//printf("%s %d %s %d %s %d\n","newh=",newh,"minf=",minf,"IG=",ImmediateGenerated);
		//string mystr;
		//getline (cin,mystr);
		//printf("%s %d\n","child h=",newh);
		maxH=MAX(maxH,newh-2);

		 newf=newh+newg;
		 if(newf<UpperLimit)
		 {
		 //Add the child to the children list
		 for(int i=0;i<SIZE;i++)
			children[ChildNum].boardState[i]=old[stateIndex].boardState[i];
		 children[ChildNum].add2Open=false;
		 children[ChildNum].g=newg;
		 children[ChildNum].h=newh;
		 children[ChildNum].PrevMove=newMove;
		 children[ChildNum].cost=minf;//newh+newg;
	//	 printf("%s %d %s %d\n","childf=",children[ChildNum].g+children[ChildNum].h,"childc=",children[ChildNum].cost);
		    //string mystr;
	//getline (cin,mystr);
		 //if(CostArr[children[ChildNum].cost]==-1) CostArr[children[ChildNum].cost]=1;
		 generated++;
		 ChildNum++;
		
		 }
		 MakeMove(stateIndex,newMove);
		// printf("%s","state after undo:");
		//for (int l=0;l<SIZE;l++)
		//	printf("%d ",old[stateIndex].boardState[l]);
		//printf("%s\n","");
	}
	//string mystr;
	//getline (cin,mystr);
//printf(" %s %d \n","***********  IG=",ImmediateGenerated);
//printf("%s\n","----------fin--------------");
	//printf("%s %d\n","maxh=",maxH);
	//Now, update the children heuristic based on maxH found:
	for (int i=0;i<ChildNum;i++)
	{
		//printf("%s %d\n","child h before change:",children[i].h);
		if(maxH>children[i].h) BLHUpdate++;
		children[i].h=MAX(maxH,children[i].h);
		if(children[i].cost<children[i].h+children[i].g) children[i].cost=children[i].h+children[i].g;
		///printf("%s %d\n","child h after change1:",children[i].h);
		//if(children[i].g+children[i].h<old[stateIndex].g+old[stateIndex].h)
		//	children[i].h=old[stateIndex].h-1;
		//printf("%s %d\n","child h after change2:",children[i].h);

		//Search for the child in memory
		hashval=CalcHash(children[i].boardState);
		newindex=SearchHash(children[i].boardState,hashval);
		if(newindex==stateIndex) newindex=-1;
		//if(newindex!=-1 && old[newindex].PrevMove!=children[i].PrevMove)
		//{
		//	printf("%s\n","different prev moves");
		//string mystr;
		//getline (cin,mystr);
		//}
		//printf("%s %d\n","newindex=",newindex);

		bool boo=true;
		// if the state already exists
		if(newindex!=-1)
		{
			
			//Check if exists in close list
			if(old[newindex].heaplink==-1)
			{
				//printf("%s","Found the state in close ");
				//for(int j=0;j<SIZE;j++)
				//	printf("%d ",old[newindex].boardState[j]);
				//printf("%s %d %s %d\n","h=",old[newindex].h," g=",old[newindex].g);
				//printf("%s %d %s %d\n","childh=",children[i].h," chilg=",children[i].g);
				//string mystr;
				//getline (cin,mystr);
				//FoundInC++;
				//if(old[newindex].h>children[i].h)
				//{
				//	children[i].h=old[newindex].h;
				//	UpdateH=true;
				//}
				if(old[newindex].g<=children[i].g)
				{
					boo=false;
					//if(old[newindex].h>=children[i].h)
					//boo=false;

				}
				//else
				//if(old[newindex].g==children[i].g && old[newindex].h>=children[i].h)
				//		boo=false;
				//if(boo) //(g in close is lower than g in children)
				else
				{
					reopened++;
					FoundInC++;
						boo=true;
						for (int j=0;j<SIZE;j++)
						old[newindex].boardState[j]=-1;
					old[newindex].h=-1;
					old[newindex].g=-1;
					old[newindex].cost=10000;
				}
				
			}// end if - if in close list
		
			//else //the node is in the open list
			if(old[newindex].heaplink!=-1)
			{
				boo=false;
				//FoundInO++;
				if(old[newindex].g>children[i].g)
				{
					reopened++;
					FoundInO++;
					//old[newindex].g=children[i].g;
					boo=false;
					if(old[newindex].h<children[i].h)
						old[newindex].h=children[i].h;
					if(old[newindex].cost!=children[i].cost) old[newindex].cost=MAX(children[i].cost,old[newindex].cost);
					FReOpen(newindex,children[i].g,children[i].PrevMove);
				}

				//---*********** this part worked ********************---
				//if(old[newindex].g>children[i].g)
				//{
				//	old[newindex].g=children[i].g;
				//	boo=false;
				//	if(old[newindex].h<children[i].h)
				//		old[newindex].h=children[i].h;
				//	ReOpen(newindex,old[newindex].g,children[i].PrevMove);
				//}
				//else //(g in close is lower than g in children)
				//{
				//	if(old[newindex].g==children[i].g)
				//	{
				//	if(old[newindex].h<children[i].h)
				//	{
				//		boo=false;
				//		old[newindex].h=children[i].h;
				//		ReOpen(newindex,old[newindex].g,children[i].PrevMove);
				//	}
				//	}
				//}//---*********** this part worked ********************---
			}
}//end if (for existing child)
		else
			boo=true;
		//boo=true; //for testing
		if (boo) 
		{
			//printf("%s\n","adding the child");
			children[i].add2Open=true;
		}
		else
		{
			//printf("%s\n","NOT adding the child");
			children[i].add2Open=false;
		}

		
	//string mystr;
	//getline (cin,mystr);
	}//end for

	//After updating the children heuristic, need to find new maxH
	//int maxLH=0;
	//for (int i=0;i<ChildNum;i++)
	//{
	//	if(children[i].add2Open==true )//&& children[i].h+children[i].g>NextBestF )
	//	{
			//if(children[i].h+children[i].g<=lookahead && children[i].h+children[i].g>NextBestF)
			//{
			//	delta=0;
			//	minf=INFINITY;
			//	//printf("%s %d %s %d %s %d %s %d\n","delta=",delta,"h=",newh,"g=",newg,"lookahead=",lookahead);
			//	int tempH=HBLookahead3(children[i].boardState,children[i].g,children[i].h,lookahead,children[i].PrevMove);
			//	//printf("%s %d %s %d\n","delta=",delta,"h=",h);
			//
			//	//printf("%s %d %s %d %s %d %s %d %s %d\n","delta=",delta,"h=",newh,"g=",newg,"tempH=",tempH,"lookahead=",lookahead);
			//	//string mystr;
			//	//getline (cin,mystr);
			//	children[i].h=MAX(children[i].h,tempH-2);
			//	//if(minf<=newh) 
			//	//{
			//	//	printf("%s %d %s %d\n","minf equals to newh after LH, minf=",minf,"newh=",newh);
			//	//	string mystr;
			//	//	getline (cin,mystr);
			//	//}
			//}
			//else
			//	minf=children[i].h+children[i].g;
			//children[i].cost=MAX(minf,children[i].cost);
		//printf("%s\n","afterLH");
		//printf("%s","the child node is:");
		//for (int l=0;l<SIZE;l++)
		//	printf("%d ",old[stateIndex].boardState[l]);
		//printf("%s\n","");
		//printf("%s %d %s %d\n","newh=",newh,"minf=",minf);
		//string mystr;
		//getline (cin,mystr);
		//printf("%s %d\n","child h=",newh);
		//maxLH=MAX(maxLH,children[i].h-2);

	//	}
	//}//end for

	//printf("%s\n","-- before insert to open --");
	// Now we can add the children to the OPEN list
	for (int i=0;i<ChildNum;i++)
	{
		if(children[i].add2Open)
		{
			//children[i].h=MAX(maxLH,children[i].h);
			if(children[i].g+children[i].h>children[i].cost) children[i].cost= children[i].g+children[i].h;
			if(children[i].cost<UpperLimit)
			{
			//printf("%s %d\n","childh before change:",children[i].h);
			//children[i].h=MAX(maxH,children[i].h);
			//printf("%s %d\n","childh after change:",children[i].h);
				hashval=CalcHash(children[i].boardState);
				if(children[i].h+children[i].g<=NextBestF)
				{
					IE++;
					int cindex=FAdd2Close(children[i].boardState,hashval,children[i].PrevMove,children[i].g,children[i].h,children[i].cost);
					 if(CostArr[children[i].cost]==-1) CostArr[children[i].cost]=1;
				//	//printf("%s %d %s %d\n","Perform IE-->NextBestF=",NextBestF,"f=",children[i].g+children[i].h);
					int r=IIBExpandNodeLH2(cindex,children[i].g,children[i].h,children[i].PrevMove,lookahead);
				//	//if (r==0) return 0;
				}
				else
				{
					//printf("%s %d %s %d\n","Adding, f=",children[i].g+children[i].h,"cost=",children[i].cost);
					 if(CostArr[children[i].cost]==-1) CostArr[children[i].cost]=1;
					FInsertHash2(children[i].boardState,hashval,children[i].PrevMove,children[i].g,children[i].h,children[i].cost);
				}
			}

		}
	}//end for
	old[stateIndex].h=MAX(old[stateIndex].h,maxH-1);

return -1;

}

void BPMXLHAStar1(short s[SIZE],int lookahead)
{
	//Variables
	int CurrentHashValue;
	int CurrentDepth;
	int CurrentOpenNode; //next node in the open list to check
	double startclock;
	double endclock;
	double innerclock;
	double time2loop;
	FILE *solution;


	//srand ( (unsigned)time ( NULL ) );
	//Init Hash table
	for (int i = 0; i< MAX; i++)                    /* empty hash table */
    {
		old[i].g = -1;                  /* only g value checked for emptiness */
		old[i].heaplink=-1;
		bucket[i] = MAX;
		old[i].cost=1000;
		for (int k=0;k<SIZE;k++)
			old[i].boardState[k]=-1;
	}

	for (int t=0;t<FULL;t++)
	{
		heap[t]=-1;
	}
	for (int i=0;i<40;i++)
		CostArr[i]=-1;


	//Init Open List pointers
	OpenStart=0; // beginning of the open list
	OpenEnd = 0; //End of the open list

	//Init next free loaction index in hash table
	empty=0;

	//Init counters
	maxopen=0;
	copen=0;
	expanded=0;                               
	generated=0;                             
	stored=0;
	reopened=0;
	opened=0;
	closed=0;
	CurrentOpenNode=0;
	ImmediateGenerated=0;
	IE=0;
	UpperLimit=1101; //TODO - need to find logical upper limit
	FoundInC=0;
	FoundInO=0;
	NextBestF=0;
	NextBestC=0;
	LHnodes=0;
	BUpdate=0;
	LHUpdate=0;
	BLHUpdate=0;
	IGSameV=0;
	LHFrom=0;
	falseLH=0;
//	UCount=0;

	//Init goal test inidicator
	CurrentDepth=0;
	//duplicateFlag = 1;
	duplicatCounter=0;
	goalDepth=0;
		//Start counting time
	startclock = (double)clock();
	CurrentHashValue=CalcHash(s);
	//Insert the initial state to the hash table and update the open list
	for (int word = 0;word<SIZE;word++)
		old[empty].boardState[word]=s[word];
	old[empty].PrevMove = SIZE;
	old[empty].g = 0;
	//ConvertStateToDual(0);
	old[empty].h=bestf=GetHuristicRegular(0,0);
	old[empty].link = bucket[CurrentHashValue];      /* next pointer to old first element */
	old[empty].heaplink=0;
	 bucket[CurrentHashValue] = empty;               /* new state is at head of hash chain */
	 int f = old[empty].g + old[empty].h; 
	 old[empty].cost=bestf;
	empty++;
	heap[0]=0;
	CostArr[bestf]=1;
	//HBLookahead3(0,0,bestf,bestf+lookahead,SIZE);
	//printf("%s %d\n","f=",old[0].h);

	//BLookahead(0,old[heap[0]].g,old[heap[0]].h,old[heap[0]].g+lookahead,old[heap[0]].PrevMove);
	//printf("%d\n",bestf);
	while (CurrentDepth!=100 && old[heap[0]].cost<UpperLimit && stored <FULL && OpenStart>=0)
	//while (CurrentDepth!=100 && old[heap[0]].g+old[heap[0]].h+lookahead<=UpperLimit && stored <FULL && OpenStart>=0)
	{
		//printf("%s %d %s\n","--Expand new node--",expanded,"----");
		//printf("%s %d %s %d %s %d\n","f=",old[heap[0]].h+old[heap[0]].g,"UpperLimit=",UpperLimit,"cost=",old[heap[0]].cost);
		//if(old[heap[0]].h+old[heap[0]].g>old[heap[0]].cost)
		//{
			//printf("%s %d %s %d %s %d\n","f=",old[heap[0]].h+old[heap[0]].g,"UpperLimit=",UpperLimit,"cost=",old[heap[0]].cost);
		//			string mystr;
		//getline (cin,mystr);
		//}
		bestf=old[heap[0]].h+old[heap[0]].g;
		bestc=old[heap[0]].cost;
		//for(int i=0;i<OpenStart;i++)
		//	if(old[heap[i]].cost<bestc)
		//	{
		//		printf("%s %d %s %d\n","bestc=",bestc,"small cost=",old[heap[i]].cost);
		//		string mystr;
		//		getline (cin,mystr);

		//	}
		NextBestC=INFINITY;
		if(OpenStart>1 )
		{
			NextBestC=old[heap[0]].cost+1;
			//printf("%s %d %s %d\n","Starting from:",NextBestC,"f=",bestf);
			// string mystr;
			//getline (cin,mystr);
			while(CostArr[NextBestC]==-1&& NextBestC<40)
				NextBestC++;
		}
		CurrentOpenNode=heap[0];
		NextBestF=old[heap[0]].h+old[heap[0]].g;
		//printf("%s %d %s %d %s %d\n","eh=",old[CurrentOpenNode].h," eg=",old[CurrentOpenNode].g,"ec=",old[CurrentOpenNode].cost);
		FDeleteFromOpenList(CurrentOpenNode); //delete the node expanded from the open list
		
				//printf("%s %d %s %d\n","NextBestF=",NextBestF,"bestc=",bestc);
		//printf("%s %d %s %d %s %d\n","UpperLimit=",UpperLimit,"lookahead=",NextBestF+lookahead,"NextBestC=",NextBestC);
		//printf("%s %d %s %d %s %d\n","f=",NextBestF,"lookahead=",NextBestF+lookahead,"NextBestC=",NextBestC);
		//string mystr;
		//getline (cin,mystr);
		int ActualLH=0;
		ActualLH=MIN(NextBestF+lookahead,NextBestC);
		if(ActualLH<bestc)
		{
			ActualLH=-1;
		}
		ActualLH=MIN(ActualLH,UpperLimit);
		//ActualLH=MIN(NextBestF+lookahead,UpperLimit);
		//printf("%s %d %s %d\n","NextBestF=",NextBestF,"lookahead=",lookahead);
		//printf("%s %d %s %d %s %d %s %d\n","f=",old[CurrentOpenNode].h+old[CurrentOpenNode].g,"UpperLimit=",UpperLimit,"cost=",old[CurrentOpenNode].cost,"lookahead=",ActualLH);
		CurrentDepth=IIBExpandNodeLH(CurrentOpenNode,old[CurrentOpenNode].g,old[CurrentOpenNode].h,old[CurrentOpenNode].PrevMove,ActualLH);
		
		expanded++;
		//printf("%s %d\n","IG=",ImmediateGenerated);
		//string mystr;
		//getline (cin,mystr);
	}
	printf("%s %d %s %d\n","heap[0].h=",old[heap[CurrentOpenNode]].h," heap[0].g=",old[heap[CurrentOpenNode]].g);
	goalDepth=UpperLimit;
	endclock = (double)clock();
	time2search = (endclock-startclock)/(double)CLOCKS_PER_SEC;
	//PrintResult2File("AStartLH",lookahead);
	PrintResult("LHA(%d)+BPMX[op.1]",lookahead);
	printf("%s\n","");
	printf("%s","expanded= ");
	printf("%d \n",expanded);
	printf("%s","IE= ");
	printf("%d \n",IE);
	printf("%s","stored = ");
	printf("%d \n",stored);
	printf("%s","reopened = ");
	printf("%d \n",reopened);
	printf("%s","IG= ");
	printf("%d \n",ImmediateGenerated);
	printf("%s","opened = ");
	printf("%d \n",opened);
	printf("%s","closed = ");
	printf("%d \n",closed);
	printf("%s %d\n","maxopen = ",maxopen);
	printf("%s","goalDepth = ");
	printf("%d \n",goalDepth);
	printf("%s", "Start Time = ");
	printf ("%f \n",startclock);
	printf("%s", "Stop Time = ");
	printf ("%f \n",endclock);
	printf("%s %d %s %d\n","LHFrom=",LHFrom,"falseLH=",falseLH);
    printf("%s %d %s %d %s %d %s %d %s %d\n","LHnodes=",LHnodes,"BUpdate=",BUpdate,"LHUpdate=",LHUpdate,"BLHUpdate=",BLHUpdate,"IGSameV=",IGSameV);
	printf("%s", "time2search = ");
	printf ("%f \n",time2search);

}





void BPMXLHAStar2(short s[SIZE],int lookahead)
{
		//Variables
	int blank;
	int CurrentHashValue;
	int CurrentDepth;
	int CurrentOpenNode; //next node in the open list to check
	double startclock;
	double endclock;
	double innerclock;
	double time2loop;
	FILE *solution;


	//srand ( (unsigned)time ( NULL ) );
	//Init Hash table
	for (int i = 0; i< MAX; i++)                    /* empty hash table */
    {
		old[i].g = -1;                  /* only g value checked for emptiness */
		old[i].heaplink=-1;
		bucket[i] = MAX;
		for (int k=0;k<SIZE;k++)
			old[i].boardState[k]=-1;
		old[i].cost=1000;
	}

	for (int t=0;t<FULL;t++)
	{
		heap[t]=-1;
	}
	for (int i=0;i<40;i++)
		CostArr[i]=-1;


	//Init Open List pointers
	OpenStart=0; // beginning of the open list
	OpenEnd = 0; //End of the open list

	//Init next free loaction index in hash table
	empty=0;

	//Init counters
	maxopen=0;
	copen=0;
	expanded=0;                               
	generated=0;                             
	stored=0;
	reopened=0;
	opened=0;
	closed=0;
	CurrentOpenNode=0;
	ImmediateGenerated=0;
	IE=0;
	UpperLimit=1101; //TODO - need to find logical upper limit
	FoundInC=0;
	FoundInO=0;
	NextBestF=0;
	NextBestC=0;
	LHnodes=0;
	BUpdate=0;
	LHUpdate=0;
	BLHUpdate=0;
	IGSameV=0;
//	UCount=0;

	//Init goal test inidicator
	CurrentDepth=0;
	//duplicateFlag = 1;
	duplicatCounter=0;
	goalDepth=0;
		//Start counting time
	startclock = (double)clock();
	CurrentHashValue=CalcHash(s);
	//Insert the initial state to the hash table and update the open list
	for (int word = 0;word<SIZE;word++)
		old[empty].boardState[word]=s[word];
	old[empty].PrevMove = SIZE;
	old[empty].g = 0;
	//ConvertStateToDual(0);
	old[empty].h=bestf=GetHuristicRegular(0,0);
	old[empty].link = bucket[CurrentHashValue];      /* next pointer to old first element */
	old[empty].heaplink=0;
	 bucket[CurrentHashValue] = empty;               /* new state is at head of hash chain */
	 int f = old[empty].g + old[empty].h; 
	 old[empty].cost=bestf;
	empty++;
	heap[0]=0;
	CostArr[bestf]=1;
	//HBLookahead3(0,0,bestf,bestf+lookahead,SIZE);
	//printf("%s %d\n","f=",old[0].h);

	//BLookahead(0,old[heap[0]].g,old[heap[0]].h,old[heap[0]].g+lookahead,old[heap[0]].PrevMove);
	//printf("%d\n",bestf);
	while (CurrentDepth!=100 && old[heap[0]].cost<UpperLimit && stored <FULL && OpenStart>=0)
	{
		bestf=old[heap[0]].h+old[heap[0]].g;
		bestc=old[heap[0]].cost;
		NextBestC=INFINITY;
		if(OpenStart>1 )
		{
			NextBestC=old[heap[0]].cost+1;
			//printf("%s %d %s %d\n","Starting from:",NextBestC,"f=",bestf);
			// string mystr;
			//getline (cin,mystr);
			while(CostArr[NextBestC]==-1&& NextBestC<40)
				NextBestC++;
		}
		CurrentOpenNode=heap[0];
		//printf("%s %d %s %d %s %d\n","eh=",old[CurrentOpenNode].h," eg=",old[CurrentOpenNode].g,"ec=",old[CurrentOpenNode].cost);
		FDeleteFromOpenList(CurrentOpenNode); //delete the node expanded from the open list
		NextBestF=old[CurrentOpenNode].h+old[CurrentOpenNode].g;
		//printf("%s %d %s %d\n","NextBestF=",NextBestF,"bestc=",bestc);
		//printf("%s %d %s %d %s %d\n","UpperLimit=",UpperLimit,"lookahead=",NextBestF+lookahead,"NextBestC=",NextBestC);
		//string mystr;
		//getline (cin,mystr);
	
		int ActualLH=MIN(NextBestF+lookahead,NextBestC);
		if(bestc>ActualLH) 
		{
			//printf("%s %d %s %d\n","no lookahead required, bestc=",bestc,"actual LH=",ActualLH);
			ActualLH=-1;
		}
		ActualLH=MIN(ActualLH,UpperLimit);
		CurrentDepth=IIBExpandNodeLH2(CurrentOpenNode,old[CurrentOpenNode].g,old[CurrentOpenNode].h,old[CurrentOpenNode].PrevMove,ActualLH);
		expanded++;
		//printf("%s %d\n","IG=",ImmediateGenerated);

	}
	printf("%s %d %s %d\n","heap[0].h=",old[heap[CurrentOpenNode]].h," heap[0].g=",old[heap[CurrentOpenNode]].g);
			//string mystr;
		//getline (cin,mystr);
	goalDepth=UpperLimit;
	endclock = (double)clock();
	time2search = (endclock-startclock)/(double)CLOCKS_PER_SEC;
	//PrintResult2File("AStartLH",lookahead);
	PrintResult("LHA(%d)+BPMX[op.2]",lookahead);
	printf("%s\n","");
	printf("%s","expanded= ");
	printf("%d \n",expanded);
	printf("%s","IE= ");
	printf("%d \n",IE);
	printf("%s","stored = ");
	printf("%d \n",stored);
		printf("%s","reopened = ");
	printf("%d \n",reopened);
		printf("%s","IG= ");
	printf("%d \n",ImmediateGenerated);
	printf("%s","opened = ");
		printf("%d \n",opened);
	printf("%s","closed = ");
	printf("%d \n",closed);
	printf("%s %d\n","maxopen = ",maxopen);
	printf("%s","goalDepth = ");
	printf("%d \n",goalDepth);
	printf("%s", "Start Time = ");
	printf ("%f \n",startclock);
	printf("%s", "Stop Time = ");
	printf ("%f \n",endclock);
	printf("%s %d %s %d %s %d %s %d %s %d\n","LHnodes=",LHnodes,"BUpdate=",BUpdate,"LHUpdate=",LHUpdate,"BLHUpdate=",BLHUpdate,"IGSameV=",IGSameV);
	printf("%s", "time2search = ");
	printf ("%f \n",time2search);

}







//-------------- MAIN -------------------------------
void main(int argc, char *argv[])
{
	short s1[SIZE]={13,14,4,5,6,11,7,8,1,0,10,15,9,12,2,3};//goal depth=10
	short goaltest[SIZE]={6,13,3,4,14,11,7,10,9,12,8,15,0,1,2,5};
	short goal[SIZE]={2,3,4,5,6,7,8,9,10,11,12,13,14,15,0,1};
	short s3[SIZE]={7,15,12,4,10,6,14,13,5,8,3,0,11,1,2,9};
	short s10[SIZE]={4,10,6,11,9,5,13,2,12,14,3,7,1,0,15,8};//goal depth=14
	FILE *states_ptr;



	//Init tables
	initHashPow();
	InitPDB();
	InitPDBParameters();
	initshouldSkipOperMat();




	//Init counters
	CaseCounter=0;

	states_ptr=fopen(ProblemsFile,"r");
    if (states_ptr==NULL){printf ("ProblemsFile not found or File can not be opened\n"); exit(0);}
	//Run search
	short tempState[SIZE];
	int oldGoalDepth;
	int casesSoFar = 10;
	//while(!feof(states_ptr) && CaseCounter<100)
	while(!feof(states_ptr) && CaseCounter<100)
	{
		CaseCounter++;
		fscanf(states_ptr,"%*d"); 
		//
		//if (CaseCounter<casesSoFar)
		//	continue;

		for(int i=0;i<SIZE;i++)
			fscanf(states_ptr,"%d",&tempState[i]);
		//if(CaseCounter<2){
		//	continue;
		//}
		printf("%s %d %s\n","-----------------",CaseCounter,"-----------------");
		for(int k=0;k<SIZE;k++)
				printf("%d ",tempState[k]);
		printf("%s\n","");
		printf("----------------- IBPMX [%d] -----------------\n",CaseCounter);
		USE_REFLECTION=true;
		IBPMXAStar(tempState);
		oldGoalDepth = goalDepth;
		printf("----------------- Classic IDA* [%d]-----------------\n",CaseCounter);
		USE_REFLECTION=false;
		GeneralIDAStar("IDA*",tempState,IDAStarIteration);
		if (goalDepth!=oldGoalDepth){
			printf("Problem");
			exit(0);
		}
		printf("----------------- IDA* with BPMX [%d]---------------\n",CaseCounter);
		USE_REFLECTION=true;
		GeneralIDAStar("IDA*+BPMX",tempState,IDAStarIterationWithBPMX);
		if (goalDepth!=oldGoalDepth){
			printf("Problem");
			exit(0);
		}
		printf("----------------- Classic A [%d]-----------------\n",CaseCounter);
		USE_REFLECTION=false;
		ClassicAStar(tempState,"A*");
		printf("----------------- IClassic A [%d]-----------------\n",CaseCounter);
		USE_REFLECTION=false;
		IClassicAStar(tempState,0);
		
		for (int i=0;i<5;i++){
			printf("----------------- LH=%d [%d] -----------------\n",i,CaseCounter);
			USE_REFLECTION=false;
			LHAStar2(tempState,i);
		}

		printf("----------------- A* with Inconsistent[%d]-----------------\n",CaseCounter);
		USE_REFLECTION=true;
		ClassicAStar(tempState,"A* with Inconsistent");

		printf("----------------- A* with BPMX [%d] -----------------\n", CaseCounter);
		USE_REFLECTION=true;
		BPMXAStar(tempState);

		for (int i=0;i<4;i++){
			printf("----------------- BPMXLH 1-%d [%d] -----------------\n",i,CaseCounter);
			USE_REFLECTION=true;
			BPMXLHAStar1(tempState,i);
		}
		for (int i=0;i<4;i++){
			printf("----------------- BPMXLH 2-%d [%d] -----------------\n",i,CaseCounter);
			USE_REFLECTION=true;
			BPMXLHAStar2(tempState,i);
		}
	}

    string mystr;
	printf("------------------- FINISHED %d Cases -----------------\n", CaseCounter);
	getline (cin,mystr);
}
